I'm looking for a simple (or better yet, minimal) example of a planar triangulation that would be "obviously" non-Hamiltonian.
Thanks in advance!
I'm looking for a simple (or better yet, minimal) example of a planar triangulation that would be "obviously" non-Hamiltonian.
Thanks in advance!
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.
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:
/\ / \ /____\ /\ /\ / \ / \ /____\/____\