Planar Eulerian graph

823 Views Asked by At

Let G be a planar Eulerian graph. Consider some planar drawing of G. Show that there exists a closed Eulerian tour that never crosses itself in the considered drawing (it may touch itself at vertices but it never “crosses over to the other side”)

I am having difficulties understanding this question. It seems obvious but I don't know how to start the proof. My instinct tells me to try contradiction but I am not sure. I am just starting with planar graphs.

1

There are 1 best solutions below

2
On

Contradiction doesn't sound promising to me. You'd have to start by assuming there is no such path, and then it's not clear what contradiction you can arrive at. I'd think it's better to show that given an Eulerian path, it's possible to modify it to have the desired property. For example, in this graphenter image description here if we have the Euler path ABEDBCA, which crosses itself, we can modify it to be ABDEBCA, which does not, by changing BEDB in the first path to BDEB in the second.

This is more a comment than an answer, but I couldn't put the picture in a comment, or describe it clearly in words.