[Math] Hamiltonian 3-regular graph

Question

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.

Answer 1

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.