Not the original poster, but one thing that confused me was that I can clearly draw a graph that cannot be two coloured with a single pen stroke if I am allowed to reverse direction and keep drawing back over the same line again (indeed it is of course possible to draw any connected graph this way). I wasn't sure which part of the conditions forbid this.
Perhaps it is no longer a graph if I have a bidirectional edge? Or perhaps it is not considered planar if two edges coincide?
Perhaps it is no longer a graph if I have a bidirectional edge? Or perhaps it is not considered planar if two edges coincide?