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]).
Best Answer
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:
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:
But these five edges cannot be completed to any Hamiltonian cycle, which is a contradiction.