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 > 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.
 A: 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$:

A: 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.
A: 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
