0
$\begingroup$

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?

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

I think you mean you have an $m \times n$ square grid graph, where, say, $m$ is even.

Hint: induct on $m/2$.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.