5
$\begingroup$

Show that every Hamiltonian 3-regular graph has at least three Hamiltonian cycles.

I think that I could use the result that says that every graph with odd vertex degree every edege lies on a even number of Hamiltonian cycles.

$\endgroup$
4
$\begingroup$

By hypothesis, you have a Hamiltonian cycle $H_1$. Choose any edge $e$ of $H_1$. Since it must lie on an even number of Hamiltonian cycles, you must have at least one more Hamiltonian cycle $H_2$. Now, $E(H_1) \setminus E(H_2) \neq \emptyset$, since otherwise $H_1$ and $H_2$ are identical. We know also that $e \notin E(H_1) \setminus E(H_2)$, since it is in both cycles. In other words, there is another edge $f \neq e$ lying on $H_1$ but not $H_2$. Since $f$ must lie on an even number of Hamiltonian cycles, there must be a third Hamiltonian cycle.

$\endgroup$
  • $\begingroup$ This answer explains why every edge of the graph lies on an even number of Hamiltonian cycles. $\endgroup$ – Rosie F Feb 23 at 17:30

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.