Show that $G_n$ contains a Hamilton cycle. this is a past paper question on my graph theory course, and I am struggling even to know when to start. The question hasn't asked me to prove anything beforehand so I don't think it warrants Dirac's Theorem or anything else. I don't know where to start!
Given $n$ is a natural number, the $n\times n$ grid is the graph $G_n$ whose vertices are the pairs $(i,j)$ for all $1\leq i,j,\leq n$ and in which any two pairs  $(i,j)$ and $(i',j')$ are joined by an edge if and only if either
(i) $i=i'$ and $|j-j'|=1$, or 
(ii) $|i-i'|=1$ and $j=j'$.
Show that $G_n$ contains a Hamilton cycle if and only if $n$ is even.
 A: First, it's not hard to exhibit a Hamiltonian circuit on a $2n\times 2n$ grid graph: use for the vertices $(i,j)$, $1\le i, j\le 2n$. Then the path 
$$(1,1)\to (1,2n)\to (2,2n)\to (2,2)\to (3,2)\to \cdots \to (2n-1,2n)\to (2n,2n)\to (2n,1)\to (1,1)$$
 is a Hamiltonian circuit. (Note, by the way, that this construction proves that there is a Hamiltonian circuit on an $m\times n$ grid graph if either $m$ or $n$ is even. In the construction above, only the horizontal coordinate needed to be even; the parity of the vertical coordinate was irrelevant.)
Now, an $m\times n$ grid graph is a bipartite graph. If $mn$ is even, then there are the same number of vertices on each "side" of the graph; if $mn$ is odd, there are not. But if a bipartite graph has different number of vertices in each of the two sides, it's clear that there cannot be a Hamiltonian circuit (suppose the graph is $(A|B)$, with $|A|>|B|$. Choose any vertex $x$ in $A$. When the vertices of $B$ are exhausted, those of $A$ are not. So the circuit cannot return to $x$.)
