It is known that every cubic Hamiltonian graph has at least three Hamiltonian cycles (by Tutte's theorem that every edge of a cubic graph belongs to an even number of Hamiltonian cycles)

Is it true that every cubic 3-connected planar Hamiltonian graph $G$ has three Hamiltonian cycles $C_1,C_2$ and $C_3$ such that every edge of $G$ belongs to exactly two of those cycles?
Clarification: we did not force that $G$ should have exactly three Hamiltonian cycles

Context: Quoting from Acyclically 4-colorable triangulations,

Observe that a triangulation $G$ ....(has property P)... if and only if its dual graph $G^*$ contains three Hamiltonian cycles such that each edge of $G^*$ is just contained in two of them. Since the problem of deciding whether a planar cubic 3-connected graph contains a Hamiltonian cycle is NP-complete[Garey,Johnson and Tarjan], we can deduce the problem of deciding whether a triangulation ....(has property P).... is NP-complete

(clarification in quote: triangulation - maximal planar graph [Not related to chordal completion] )

From their words, it sounds like the answer to the question is yes. But I am clueless as to why. I could not find any counter example either.

If there were constructions to make second (and third) Hamiltonian cycle from a given one, then the construction might be of use. But this is a hard problem in itself (even when the graph is guaranteed to have more than one Hamiltonian cycle).

It is easy to see that a cubic Hamiltonian graph has a 3-edge colouring. But, that doesn't seem to help either . (If we have a 3-edge colouring such that subgraph induced by edges coloured 1,2 is a Hamiltonian cycle, from that alone we can not say that edges coloured 2,3 (or 1,3) will form a Hamiltonian cycle. [I think most of the time they will not be]).

  • $\begingroup$ A closely related notion is Multiple Hamiltonian Cover(MHC) introduced in Some basic properties of multiple Hamiltonian covers [sciencedirect.com/science/article/pii/S0166218X06001375] $\endgroup$ – Cyriac Antony May 22 '19 at 8:53
  • $\begingroup$ Using the terminology of the paper in the above comment, we are asking whether every cubic 3-connected planar Hamiltonian graph has a Hamiltonian 2-cover consisting of three Hamiltonian cycles. That paper also points out that a cubic graph has a Hamiltonian 2-cover iff it is strongly Hamiltonian. $\endgroup$ – Cyriac Antony May 23 '19 at 5:05

It is not true that three such cycles always exist; the cube graph is a counterexample. (Moreover, you are right that this is a hole in the proof; it is plausible that it might be NP-hard to test if a 3-connected planar cubic graph is Hamiltonian, but not NP-hard to test if a 3-connected planar cubic graph has a $3$-coloring in which any two color classes form a Hamiltonian cycle.)

This can be checked by brute force, since there are only six Hamiltonian cycles, and each of them looks like the following one up to an automorphism of the graph:

enter image description here

But once we draw a cycle, there is limited freedom to draw the two others, and we run into a contradiction quickly when we try to do it by hand.

If $C_1$ is the cycle above, then $C_2$ and $C_3$ must both include the $4$ edges that are not part of $C_1$. In addition, one of $C_2$ or $C_3$ must include the horizontal edge in the middle right of the diagram, giving us the following five edges:

enter image description here

But these five edges cannot be completed to any Hamiltonian cycle, which is a contradiction.

  • $\begingroup$ Oops, my mistake. I forgot the condition 'planar'. Thank you for your effort. $\endgroup$ – Cyriac Antony May 23 '19 at 4:36
  • $\begingroup$ I shall ask a new question (actually what I wanted to ask) taking cue from math.meta.stackexchange.com/q/29761/120721 $\endgroup$ – Cyriac Antony May 23 '19 at 4:42
  • $\begingroup$ On further thought, I am not asking a new question. The counterexample you have given would work even when the condition planarity is included as $Q_3$ is planar. I shall edit the question. $\endgroup$ – Cyriac Antony May 23 '19 at 4:58

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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