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 $y$ou so much! Based on your e$x$planation 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:

     /\     /  \    /____\   /\    /\  /  \  /  \ /____\/____\ 
  • 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