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 that would be "obviously" non-Hamiltonian.

Thanks in advance!

share|improve this question
add comment

3 Answers

up vote 4 down vote accepted

If one starts with a graph which has more faces than vertices (all of whose faces are triangles), for example the graph of the octahedron, and erects a pyramid on each face, one gets a graph all of whose faces are triangles and which can not have a hamiltonian circuit.

Non-hamiltonian 3-polytopal graph

This process will work for constructing non-hamiltonian polytopes in higher dimensions, and is sometimes known as a Kleetope because Victor Klee called attention to this idea.

share|improve this answer
    
This is a great example, thank you so much! Based on your explanation I think I could build a slightly simpler one (1 less vertex in the original graph, before erecting the pyramids). It doesn't seem to be even semi-Hamiltonian. Cheers! –  Yann David Nov 6 '11 at 0:11
add comment

You might be interested in the following theorem of Whitney: Let $G$ be a planar graph all of whose faces are triangles (including the outside face). Assume that $G$ has no loops, no multiple edges, and that every $3$-cycle of $G$ bounds a face. Then $G$ has a Hamiltonian cycle.

Note that Joseph Malkevitch's example violates the bolded condition.

share|improve this answer
add comment

This would seem to be minimal:

     /\
    /  \
   /____\
  /\    /\
 /  \  /  \
/____\/____\
share|improve this answer
1  
Isn't the cycle defined by the outermost edges a Hamiltonian cycle? –  Austin Mohr Nov 4 '11 at 0:13
    
@Austin: The question doesn't define a Hamiltonian triangulation. I went by the definition in this paper, which says: "[...] a triangulation is Hamiltonian if its dual graph contains a Hamiltonian path." –  joriki Nov 4 '11 at 0:30
    
I read it to mean "the graph corresponding to the triangulation is a Hamiltonian graph" (i.e. contains a Hamiltonian cycle). Your interpretation is probably what OP intended, though perhaps s/he can clarify. –  Austin Mohr Nov 4 '11 at 0:56
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.