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&#x27;t sure which part of the conditions forbid this.<p>Perhaps it is no longer a graph if I have a bidirectional edge?  Or perhaps it is not considered planar if two edges coincide?