$\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$

3 Answers

$\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.

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$ 1 $\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$ $\begingroup$

This would seem to be minimal:

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

$\endgroup$ 3

Your Answer

Sign up or log in

Sign up using Google Sign up using Facebook Sign up using Email and Password Submit

Post as a guest

Post Your Answer Discard

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