# Proof for hamiltonian cycle in grids having even no. of nodes

How can I go about proving that an undirected graph having even no. of nodes (at least one of the rows or columns are even - excluding line graphs of course) have a hamiltonian cycle?

I have managed to come as far as to prove that it is a bipartite graph and (as a result ) has all cycles of even length.

But exactly how can I show that at least one such cycle exists that covers all the available nodes?

• Your question appear to be incomplete. A graph having an even number of nodes is not necessarily hamiltonian. – Jernej Nov 8 '13 at 14:53

I think you mean you have an $m \times n$ square grid graph, where, say, $m$ is even.
Hint: induct on $m/2$.