Skip to main content
1 of 5
EGME
  • 1k
  • 8
  • 14

Hamiltonian cycles containing all chords of a given Hamiltonian cycle in almost cubic Hamiltonian graphs

Let $G$ be a 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 question is:

Question (EGME) Let $G$ be a cubic graph which has a Hamiltonian circuit $C$. Is it always possible to add a chord of $C$ in $G$ so that the resulting graph has a Hamiltonian circuit containing all the chords? Please provide proof or counterexample.

Computer experiments seem to suggest this might be the case.

EGME
  • 1k
  • 8
  • 14