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!

$\endgroup$
2
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ Thanks, that's a very enlightening answer - and exactly what I was looking for: I implicitly included the exterior face, "working on a sphere". $\endgroup$ – Yann David May 9 '12 at 0:00
2
$\begingroup$

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.

$\endgroup$
  • 1
    $\begingroup$ 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? $\endgroup$ – lhf May 7 '12 at 0:23

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.