0
$\begingroup$

I'm trying to prove using Smith's theorem (each edge on a cubic graph is contained in an even number of hamilton cycles) that if $G$ is $3-$regular and Hamiltonian then there exist at least three Hamilton cycles.
My idea was that since we already know the existence of a Hamiltonian cycle $C$, we can take an arbitrary vertex, $v$. For this $v$ we know that two out of three edges adjacent to it (say $e_1,e_2$) are being used for $C$. These two edges must be contained in at least one more hamilton cycle each, say $C_1, C_2$. If these two cycles do not coincide then we are done. But what about $C_1$ being the same with $C_2$? Then we could use the third edge to get another Hamilton cycle. So in order to complete the proof what i need is either an argument that allows me to say $C_1 \neq C_2$ (which i doubt) or an argument that makes sure that there exists a vertex $v \in V(G)$ such all three edges are contained in a hamilton cycle (and therefore in a non-zero even number of them).
So, assuming that all vertices have an edge adjacent that is not contained in any hamilton cycle i have trouble deducting a contradiction.
any hint on this would be appreciated.

$\endgroup$
4
$\begingroup$

We know that the graph contains a Hamiltonian cycle $H_1$. We choose an edge $e$ of $H_1$. We know from Smith's theorem that $e$ belongs to an even number of Hamiltonian cycles, therefore there exists a second Hamiltonian cycle $H_2$.

Now, we know that $E(H_1)\backslash E(H_2) \neq \emptyset$ (otherwise we would have that $H_1=H_2$). We also know that $e \not\in E(H_1)\backslash E(H_2)$. Therefore, there exists an edge $e'\neq e$ that belongs to $H_1$ but not $H_2$. From Smith's theorem again, we know that $e'$ belongs to an even number of Hamiltonian cycles, therefore there exists a third Hamiltonian cycle $H_3$.

$\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.