# Showing that the infinite grid is Eulerian

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?

-
One of the other replies in that thread said that diamond-shaped aggregations are finite and Eulerian. So maybe you can work your way out, doing bigger and bigger diamonds. –  Gerry Myerson Dec 15 '12 at 5:31
@GerryMyerson, I didn't get what Eppstein said about an even sided diamond shaped region. That would include the particular case of squares, but I can't even see the case for squares! :) OTOH, I am following (again) his hint of walking the edges of the graph such that the endpoints of a visited region of the graph always lie on its border and it has been working so far for a drawing... I am distilling some observations, but I don't know if I will be able to transform them into an algorithm to cover the whole graph. Let's see how things progress now. :) –  rbrito Dec 15 '12 at 6:10

How do you get from the 5th step to the 6th step? In the 5th step, let's call the two extremes $u$ (at the left) and $v$ (at the right). The only way that I see that jump is to get $v$, visit 3 sides of the upper square and then finish there at the top. Is this right? You are basically just walking with one of the endpoints, right? But in your last figure, how do you get of the dead-end? –  rbrito Dec 15 '12 at 6:04