1
$\begingroup$

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 ?

$\endgroup$
3
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ @Roeny: Please specify which part you don't understand. $\endgroup$ – joriki Apr 5 '16 at 16:15
  • $\begingroup$ @Roeny: The picture was meant to illustrate that. It has $m=5$ and $n=6$. Start, say, in the lower left corner, go up all the way, one to the right, down almost all the way, leaving one row free, one to the right, back up, one to the right, back down, one to the right, back up, one to the right, now all the way down to the lower right corner, and use the row that you left free to return to the lower left corner. $\endgroup$ – joriki Apr 5 '16 at 16:42

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.