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.
For a proof by induction, consider this: Without loss of generality, consider $m$ even and $n$ a natural number greater than 1 (because else we would only have a path). Induction start $m=2$ is obvious, for example take the counter-clockwise path $$(1,1),(2,1),(2,2)\ldots,(2,n-1),(2,n),(1,n),(1,n-1),\ldots,(1,2),(1,1).$$
Now the induction step $m\mapsto m+2$: We can imagine our $(m+2)\times n$ grid as an extension of the $m\times n$ grid by two additional rows of $n$ vertices each. Now the $m\times n$ grid has a Hamiltonian cycle by induction hypothesis, say $C_m=v_1,v_2,\ldots, v_\ell, v_1$. We can assume that $v_1=(1,1)$ and $v_2=(2,1)$ (because we can shift and reverse the cycle if needed and from $(1,1)$ you can only go to $(1,2)$ or $(2,1)$).
We know that $(m,1)$ will be the next corner met by the cycle (because else to meet all corners and go back to $(1,1)$ we would have to visit a vertex twice), say $v_k = (m,1)$ with $1<k<\ell$. We also know that $v_{k-1}=(m-1,1)$ (for the same reason as before), and so $v_{k+1}=(m,2)$ (because that is the only way the cycle can go in the $m\times n$ grid).
What we do next is replacing the edge $v_kv_{k+1}$ by a detour through our $2n$ added vertices, counter-clockwise as above. Hence we get a Hamiltonian cycle, completing: $$C_{m+2}=v_1,...,v_k,(m+1,1),(m+2,1),\ldots,(m+2,n),(m+1,n),\ldots,(m+1,2),v_{k+1},\ldots, v_\ell,v_1$$
As for why both odd don't work, we can check that the $3\times 3$ grid does not have a Hamiltonian cycle (because the corners already dictate a cycle that cannot visit the inner vertex), but I can't seem to find an induction or minimal counterexample proof.
But consider this: When we start in $(1,1)$, to get back to it in a Hamiltonian cycle, every time we go a step in the first or second coordinate, we have to step back again (you can see this nicely on the walks I described above). So we have an even number of steps in our walk. But each step means a new unvisited vertex (or the first one, but we only count it once because it wasn't counted by a "step 0"), so even number of steps means even number of vertices, but $mn$ is odd as the product as two odd vertices. This is why it doesn't work.