Hamilton paths/cycles in grid graphs

Question

Let G be a grid graph with m rows and n columns, i.e. m = 4, n = 7 is shown here:

For what values of m and n does G have a Hamilton path, and for what values of m and n does G have a Hamilton cycle?

So far I've figured out that a grid graph always has a Hamilton path, and has a Hamilton cycle when at least one of m or n is even. I'm struggling to provide justification as to why this is true...

Answer 1

HINT: You simply need to explain carefully how to produce the desired paths.

• There is always a Hamilton path that simply traverses the rows in alternate directions.

• If, say, $m$ is even, as in your example, you can generalize the following idea (which I’ve left slightly incomplete). The evenness of $m$ is what makes the idea work.

    *-->*-->*-->*-->*  
                    | 
                    V  
    *   *<--*<--*<--*  
        |  
        V  
    *   *-->*-->*-->*  
                    |  
                    V  
    *<--*<--*<--*<--*
  

Answer 2

To prove why it works when $mn$ is even and $m, n > 1$ it should be enough to provide a construction of a Hamiltonian cycle as Brain did in his answer.

To prove why there is no such cycle when $mn$ is odd consider the following: color each vertex as "black" when the sum of its coordinates is even otherwise as "white". In this way you get a checkerboard pattern and no likewise colored vertexes are connected. Since the total number of vertexes is odd the start and endpoints of a Hamiltonian path must have the same colors, therefore they can not be connected.