MathOverflow is a question and answer site for professional mathematicians. It only takes a minute to sign up.
Sign up to join this community
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?
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.
