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!

$\endgroup$
6
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ 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! $\endgroup$ – Yann David Nov 6 '11 at 0:11
2
$\begingroup$

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.

$\endgroup$
0
$\begingroup$

This would seem to be minimal:

     /\
    /  \
   /____\
  /\    /\
 /  \  /  \
/____\/____\
$\endgroup$
  • 2
    $\begingroup$ Isn't the cycle defined by the outermost edges a Hamiltonian cycle? $\endgroup$ – Austin Mohr Nov 4 '11 at 0:13
  • $\begingroup$ @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." $\endgroup$ – joriki Nov 4 '11 at 0:30
  • $\begingroup$ 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. $\endgroup$ – Austin Mohr Nov 4 '11 at 0:56

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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