Skip to main content
5 of 5
added 136 characters in body
EGME
  • 1k
  • 8
  • 14

Extending perfect matchings into Hamiltonian cycles

Let $G$ be a simple cubic graph which has a Hamiltonian circuit $C$. In general, it is not possible to find a second Hamiltonian circuit which contains all the chords of $C$. For example, the Wagner graph with $C$ being the outer circuit in the picture contains no such second Hamiltonian circuit.

Wagner graph

But it is possible to add an additional chord so that the resulting graph contains a second Hamiltonian circuit including all chords, as in the second picture?

Wagner with chord

Our first question is:

Question 1 (EGME) Let $G$ be a cubic graph which has a Hamiltonian circuit $C$ with a set of chords $D$. Is it always possible to add a chord $f$ of $C$ in $G$ so that the resulting graph has a Hamiltonian circuit containing all the chords (including the new chord $f$)? Or equivalently, is there a Hamiltonian path containing all the chords in D? Please provide proof or counterexample.

Our second question is

Question 2 (EGME) If we add ANY new set of chords of $C$ in $G$ (as in question 1) which are a perfect matching in the resulting graph (which should be simple), is there a second Hamiltonian circuit which contains all of the chords in the original set? Or equivalently, let $G$ be a 4-regular Hamiltonian graph $G$ with a Hamiltonian circuit $C$, and such that the chords of $C$ can be partitioned into two perfect matchings $P$, $Q$. Is there a Hamiltonian circuit of $G$ which contains all the edges in $P$ ($Q$). If not, under what conditions is this true?

Computer experiments seem to suggest this might be the case.

EGME
  • 1k
  • 8
  • 14