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?
Best Answer
Spiral around, leaving one half-row unoccupied, then approach the origin from infinity on the left: