2
$\begingroup$

I'm looking for a simple (or better yet, minimal) example of a planar triangulation of which dual graph (that of the faces) would be "obviously" non-Hamiltonian.

(NB: I once asked the same question for planar triangulations, but I'm now interested in their dual graphs.)

Thanks in advance!

2 Answers 2

2

As discussed in the comments to Gerry Myerson's answer, I am assuming you want to work on a sphere, so that there is a vertex assigned to the outer face. If not, then Gerry's answer gives a simple counter-example.

The statement is still false if you include the extrerior face. You want the planar dual of the Tutte graph. As discussed at the link, Tait conjectured that any three-regular three-connected planar graph is Hamiltonian. Proving this for planar graphs would have implied the 4 color theorem, so people were pretty excited about this conjecture until Tutte broke it. The smallest known counterexample has 38 vertices.

It is true that almost all three-regular graphs are Hamiltonian. Here is a survey on Hamiltonian cycles in three-regular graphs.

  • 0
    Thanks, that's a very enlightening answer - and exactly what I was looking for: I implicitly included the exterior face, "working on a sphere".2012-05-09
2

Take a triangle, connect the midpoints of the edges to form a figure of four triangles, an inner triangle with three other triangles incident to it. The dual graph is a tree with a central vertex joined to three other vertices, and that's not Hamiltonian.

  • 1
    The dual usually contains also the exterior face. OTOH the OP did not mention this. In other words, is this a problem in the plane or on the sphere?2012-05-07