4
$\begingroup$

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?

Some additional facts (possibly relevant):

  • 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)

$\endgroup$
4
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ We still need to check if it remains Non Hamiltonian - is that easy to see? $\endgroup$ – SamiD Apr 11 '14 at 15:16
  • $\begingroup$ Besides I think this operation does not change the parity of the degrees. $\endgroup$ – SamiD Apr 11 '14 at 15:18
  • $\begingroup$ 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. $\endgroup$ – domotorp Apr 11 '14 at 18:41
  • $\begingroup$ 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. $\endgroup$ – SamiD Apr 12 '14 at 2:26

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.