# Dual Barnette's Conjecture

Is every Eulerian triangulated (planar) graph Hamiltonian?

On the other hand we have that:

Barnette's Conjecture (Open): Every cubic bipartite (3-connected) planar graph is Hamiltonian.

Notice that: Eulerian triangulated planar graphs and cubic bipartite planar graphs are mutual duals.

I would be happy to know of a proof or a counterexample (I have not been able to find either). In the absence of both is this a well known conjecture?

• Every Eulerian triangulated planar graph is $3$-colorable (see this).
• (Whitney's Theorem) Every $4$-connected triangulated planar graph is Hamiltonian.

Definitions:

• Hamiltonian Graph: Undirected Graph with a simple cycle through every vertex.
• Eulerian Graph: Connected graph with all degrees even.
• Triangulated (planar) Graph: Planar graph with every face a triangle.
• Cubic Graph: Graph with every vertex having degree exactly $3$.

Edit: (Thanks@domotorp) Triangulated planar graphs are not necessarily Hamiltonian (e.g. see this)

Maybe I am mistaken but I think it is possible to make the example from https://math.stackexchange.com/a/78835/131224 Eulerian. Just take an octahedron and place 3 new vertices on each of its faces, connected to each other and also to two of the vertices of the face in a circular order. So if the face was $abc$, then add $def$ and connect $d$ to all but $a$, $e$ to all but $b$ and $f$ to all but $c$. The same reasoning works but now every degree is even.

• We still need to check if it remains Non Hamiltonian - is that easy to see? – SamiD Apr 11 '14 at 15:16
• Besides I think this operation does not change the parity of the degrees. – SamiD Apr 11 '14 at 15:18
• It is easy to see that this is also Non-Hamiltonian; as the original octahedron had more faces than vertices, there is a face (of the original octahedron, now containing vertices) that we cannot enter. The parity of the degrees don't change, which is good, as they were all even in the beginning. – domotorp Apr 11 '14 at 18:41
• OK! so now I begin to understand the argument about the Kleetope. So what you are saying is that you add a triangle inside each of the original faces of an octahedron (instead of stellating it), this wuld introduce 3 vertices per face, so because the octahedron had 6 vertices and 8 faces, this new graph has 6 old vertices and 8x3 new vertices so since each of the 8 sets of vertices consumes at least one old vertex on the average we cannot have a Hamiltonian cycle. And the graph is clearly Eulerian - because the octahedron is. I think that is correct. – SamiD Apr 12 '14 at 2:26