Why there's no hamiltonian cycle for a grid where $m$ and $n$ are odd?

Question

I have read some of the discussions about the topic but while I understand that a grid $n$ x $m$ with $n$ or $m$ even ($n,m>1$) has always an hamiltonian cycle I don't get the reasoning behind the checker colouring argument to prove the non-existence of a cycle when $m$ and $n$ are odd. Can someone better clarify the argument?

Answer 1

There actually is a Hamiltonian path; there just isn’t a Hamiltonian circuit. (E.g., one can start at the upper left corner, go across the top row from left to right, then back from right to left across the second row, and so on, ending up at the lower righthand corner.)

When the vertices are colored alternately black and white in checkerboard style, every move from one vertex to an adjacent vertex is a move either from a white vertex to a black one or from a black vertex to a white one. In other words, every time you move, you change the color of the vertex on which you’re standing.

Say that you start on a white vertex. Your first move takes you to a black vertex; your second move takes you to a white vertex; your third move takes you to a black vertex; and so on. This means that after an odd number of moves you’re at a black vertex, and after an even number of moves you’re at a white vertex.

Suppose that you’ve made a Hamiltonian circuit. It takes you back to your original vertex, so at the end of it you’re on a white vertex. That means that you must have made an even number of moves, as an odd number of moves would have put you on a black vertex. Let’s number the vertices in the order in which you reached them. We’ll take $v_0$ as the white vertex at which you started; then $v_1$ is the black vertex that you reached on your first move, $v_2$ is the white vertex that you reached on your second move, $v_3$ is the black vertex that you reached at the end of your third move, and so on. Note that $v_i$ is always black when $i$ is odd and white when $i$ is even. If your circuit took $k$ moves, so that the last vertex that you reached is $v_k$, then $v_k$ must be your starting vertex: $v_k=v_0$. That’s a white vertex, so $k$ must be an even number.

On the other hand, you must have visited every vertex: the vertices $v_1,v_2,v_3,\ldots,v_k$ must be all of the vertices in the graph, each listed exactly once, since a Hamiltonian circuit cannot repeat any vertex except the starting/ending vertex. Thus, $k$ must be equal to the number of vertices in the graph. But the $m\times n$ grid graph has $mn$ vertices, and if $m$ and $n$ are both odd, so is $mn$, and therefore $k$ must be odd.

This is a contradiction: on the one hand $k$ must be even, and on the other hand it must be odd. This being impossible, we conclude that there simply is no Hamiltonian circuit on the $m\times n$ grid graph when $m$ and $n$ are both odd.