Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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:

The infinite square grid is Hamiltonian

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?

share|improve this question
    
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
add comment

1 Answer 1

up vote 2 down vote accepted

Spiral around, leaving one half-row unoccupied, then approach the origin from infinity on the left:

share|improve this answer
    
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
1  
From 5th to 6th, you are correct, it is right, up, left, up. The last figure is three steps before the actual last step. The dead end completes the circuit. The ellipsis above the word "is" represents an infinite number of steps, so the last two figures fill the plane except for the incomplete middle row. –  Dan Brumleve Dec 15 '12 at 6:15
    
The definition of Eulerian given in the book for infinite graphs is that you simply have a path that extends from its two end vertices indefinitely, is allowed to pass through any vertex any number of times, but each edge only a finite number of times. –  rbrito Dec 15 '12 at 6:17
    
Your explanation of what you meant with the ellipsis is helpful in understanding what you meant. But there is one problem, though, if I were to transform this into a proof by induction: after I traversed the whole plane, how do you define "the last 3 or 4 or 5" last steps? Perhaps I misunderstood you? –  rbrito Dec 15 '12 at 6:22
    
Well, instead of going out towards infinity, and then coming back in from infinity, you can think of each edge being assigned to an integer, where the negative integers correspond to the edges leading left away from the origin, and the positive integers correspond to the edges spiraling around. It is a bijection and consecutive integers map to adjacent edges. It shouldn't be too hard to find an explicit formula for the location of each edge in terms of the integer it corresponds to. –  Dan Brumleve Dec 15 '12 at 6:25
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.