4
$\begingroup$

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

Thanks in advance!

3 Answers 3

6

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.

  • 0
    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!2011-11-06
2

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.

0

This would seem to be minimal:

     /\
    /  \
   /____\
  /\    /\
 /  \  /  \
/____\/____\
  • 2
    Isn't the cycle defined by the outermost edges a Hamiltonian cycle?2011-11-04
  • 0
    @Austin: The question doesn't define a Hamiltonian triangulation. I went by the definition in [this paper](http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.79.8718&rep=rep1&type=pdf), which says: "[...] a triangulation is Hamiltonian if its dual graph contains a Hamiltonian path."2011-11-04
  • 0
    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.2011-11-04