# Trivial example of a non-Hamiltonian planar triangulation?

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

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.

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.

• 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

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.

This would seem to be minimal:

     /\
/  \
/____\
/\    /\
/  \  /  \
/____\/____\

• 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