In a post to usenet in 2004, I wrote:
I'm currently remembering learning [sic] some (long forgotten) things about Graph Theory via Robin J. Wilson's "Introduction to Graph Theory", 2nd. ed., 1972.
Unfortunately, I'm having a hard time with one of the exercises, which asks for the reader to show that the infinite square grid is an Eulerian graph by showing an explicit two-way Eulerian path (i.e., one path that covers every edges of the graph and that extends in both directions).
Where can I find a hint for this excercise?
At that point, I had already seen that the infinite square grid (considering only the vertical or horizontal lines as being the "edges" of the grid) is Hamiltonian by a simple drawing of two "concentric" spirals, as the following figure shows:
One of the replies that I received was from David Eppstein, who told me: "Hint: spiral."
Unfortunately, I have revisited the problem from time to time and I have not found a way to solve it. I asked some colleagues and they were not also able to come up with an answer.
So, how can one systematically traverse all the edges of the unit grid without getting stuck at some point by the two-sided infinite path bumping into itself?