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.
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?
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.
