Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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!

share|improve this question
add comment

2 Answers

up vote 2 down vote accepted

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.

share|improve this answer
    
Thanks, that's a very enlightening answer - and exactly what I was looking for: I implicitly included the exterior face, "working on a sphere". –  Yann David May 9 '12 at 0:00
add comment

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.

share|improve this answer
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? –  lhf May 7 '12 at 0:23
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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