Q:

Prove $P_m X P_n$ is Hamiltonian if and only if at least one of $m,n$ is even

How to prove "Prove $P_m X P_n$ (graph cartesian product) is Hamiltonian if and only if at least one of $m,n$ is even"
Graph cartesian product is Grid graph, if I figure out $P_2 X P_2$ it will be $C_4$ (it is Hamiltonian). How to state this prove ?

A:

If at least one of $m$ and $n$ is even, you can alternatingly go up and down in that direction, sparing one row of the other direction to complete the cycle. An example in ASCII art:
/\ /\ /\
|| || ||
|| || ||
| V  V |
\------/

If both $m$ and $n$ are odd, the total number of vertices is odd, and if you checker them black and white a Hamiltonian cycle has to connect equal numbers of each colour, which is impossible since there are different numbers of them because the sum is odd.

