0
$\begingroup$

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?

$\endgroup$
3
  • 4
    $\begingroup$ True. The number of Hamilton cycles through any edge of a cubic graph is even. $\endgroup$ Oct 22, 2013 at 12:49
  • $\begingroup$ This actually follows from a comment of domotorp at your question: mathoverflow.net/questions/152204/… $\endgroup$ Dec 31, 2013 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, 2014 at 1:38

1 Answer 1

3
$\begingroup$

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.

$\endgroup$
2
  • $\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, 2013 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, 2016 at 15:01

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.