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)

Improve this question
$\endgroup$
0

1 Answer 1

Reset to default
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.

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

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

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