Eulerian path question

Question

I was hanging out with a friend of mine the other day and we showed each other some riddles, so I showed him the standard house with an x Eulerian path riddle. For those who are unfamiliar, the riddle is basically: can you draw a house with an X (a square with an equilateral triangle on top, and the two diagonals of the square) without tracing the same line twice and without taking the pencil off of the paper. So I showed him one of the many solutions, and he was dissatisfied because my solution involved two lines crossing each other. So the question is: is there any proof that any given Eulerian path can be solved without crossing any lines? Two corners can touch each other, but no lines can cross each other.

Answer 1

Yes, this can always be done, not just with the house problem, but in general.

One simply way of seeing this is as follows. Instead of drawing it, imagine laying it out with a long piece of thread. If the thread never crosses itself, then you've already found a solution without crossings. Suppose therefore that you do have a crossing somewhere.

To get rid of the crossing, you can cut the threads at the crossing point so you have four loose ends meeting at a point. Now reconnect the threads by tying them together in two pairs, but so that they do not cross. There are two ways of doing this - you change the crossing X to either >< or the same rotated by 90 degrees. One of those two ways would split the thread into two separate parts by creating a loop, but the other will keep the thread as a single long piece, so choose the latter. In this way you have removed one crossing.

Now just repeat the above procedure until there are no crossings left.