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 > 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 p. (2011). ZBL1237.68004.
Best Answer
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$: