# Does this graph contain at least two Hamiltonian cycles?

Let $G$ be a simple graph which is a $2n$-cycle together with $n$ chords such that $G$ is $3$-regular. In other words, the set of $n$ chords is a perfect matching of $G$.

I conjecture that for every such graph $G$, there must exist at least two different $2n$-cycles in $G$. Can you prove it or give a counterexample?

• True. The number of Hamilton cycles through any edge of a cubic graph is even. – Gordon Royle Oct 22 '13 at 12:49
• This actually follows from a comment of domotorp at your question: mathoverflow.net/questions/152204/… – Daniel Soltész Dec 31 '13 at 17:37
• Hello,Daniel Soltész,Sorry to answer you so late.I asked this question much earlier than the question you mentioned above when I really did not know Smith's theorem.In fact,this question is just the simplest situation that derive from my later question:mathoverflow.net/questions/152204/…. – user40096 Mar 17 '14 at 1:38

Claim. Let $G$ be a $d$-regular graph with $d$ odd. Then for every $e \in E(G)$, there is an even number of Hamiltonian cycles using $e$.
Proof. Let $e=uv$ and let $\mathcal{H}$ be the set of Hamiltonian paths in $G$ that start at $u$ and use the edge $e$. Suppose that $P$ is such a path with ends $u$ and $w$. Note that for any edge $wv$ with $v \neq u$, there is exactly one other Hamiltonian path $P_{wv} \in \mathcal{H}$ contained in $P \cup \{wv\}$. Create an auxiliary graph $G'$ with $V(G')=\mathcal{H}$ and if $P \in \mathcal{H}$ has ends $uw$, then $P$ is adjacent to $P_{wv}$ for all edges $wv$ with $v \neq u$. Finish by observing that there is a 1-1 correspondence between Hamiltonian cycles in $G$ using $e$ and odd-degree vertices of $G'$. Hence, there are an even number of them, as required.
• Tony Huynh，Thank you very much.In your claim,the condition "$d$-regular" can be turned into "the degree of every vertex is odd". – user40096 Oct 26 '13 at 2:29
• Is there any analogue of the Claim for the case when you're interested in edge-disjoint Hamilton cycles? e.g. if $G$ is $5$-regular and contains a Hamilton cycle, might it be true that there is always a 2nd Hamilton cycle which shares no edges with the first? (I guess no for trivial edge-connectivity reasons, so maybe rule that out as well.) – user62562 Feb 5 '16 at 15:01