Induction on grid Hamiltonian graph This exercise is thaken from [1]:


  1.7 A rook’s tour. Let $G$ be an $m \times n$ grid—that is, a graph with $m n$ vertices arranged in an $m \times n$ rectangle, with each vertex connected to its nearest neighbors. Assume that $m , n &gt; 1$. Prove that $G$ is Hamiltonian if either $m$ or $n$ is even, but not if both $m$ and $n$ are odd.


I claim that for $m=1$ I can't find any Hamiltonian cycle. For $m=2$ I can find one Hamiltonian cycle. 

There is a way to generalize this in order to obtain a proof by induction (on $m$, on both $m, n$)?

[1] Moore, Cristopher; Mertens, Stephan, The nature of computation, Oxford: Oxford University Press (ISBN 978-0-19-923321-2/hbk). xvii, 985&nbsp;p. (2011). ZBL1237.68004.
As noted in the comments; coloring the vertices black and white in a chessboard pattern, in any path the colors of the vertices will alternate. So if $m$ and $n$ are both odd, then the color of the $mn$-th vertex is the same as the color of the first vertex, so no Hamiltonian cycle exists.

Otherwise, without loss of generality $m$ is even. Start at the top left, move along the top row (of length $n$) to the top right corner. Then move down to the bottom right corner, and zigzag up and down all the way back until you reach the top left corner. For example, if $m=6$ and $n=7$:
As already mentioned in the comments colour the tiles Black and White similar to a chessboard.

Notice that each white cell is horizontally or vertically connected to a black cell.

WLOG lets start from a white cell. Now you must go to a black cell, then a white cell and so on.

This means that

number of white cells$=$number of black cells, Hence $mn$ must be even