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?

  • 4
    $\begingroup$ True. The number of Hamilton cycles through any edge of a cubic graph is even. $\endgroup$ – Gordon Royle Oct 22 '13 at 12:49
  • $\begingroup$ This actually follows from a comment of domotorp at your question: mathoverflow.net/questions/152204/… $\endgroup$ – Daniel Soltész Dec 31 '13 at 17:37
  • $\begingroup$ 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/…. $\endgroup$ – user40096 Mar 17 '14 at 1:38

Here is a proof of Gordon's claim. We will prove something slightly stronger.

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.

Since your graph has at least one Hamiltonian cycle, it necessarily has at least two of them by the claim.

  • $\begingroup$ Tony Huynh,Thank you very much.In your claim,the condition "$d$-regular" can be turned into "the degree of every vertex is odd". $\endgroup$ – user40096 Oct 26 '13 at 2:29
  • $\begingroup$ 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.) $\endgroup$ – user62562 Feb 5 '16 at 15:01

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.