# Does a planar triangulation always contain a Hamiltonian path?

What about a Hamiltonian path in a triangulation of an n-gon? If not, how long is the longest path?

## 3 Answers

There are two planar triangulations on 14 vertices without hamiltonian paths. This is the smallest size. For sure these are well-known. Those answer the question for $n=3$. For $n=4$ the first examples appear at 12 vertices. Same for $n=5$. For $n=6$ one with 10 vertices. For $n=7$ one with 11 vertices. And so forth.

It is a famous theorem of Whitney (1931*) that a $4$-connected planar triangulation has a Hamiltonian cycle. Example of non-Hamiltonian triangulation from Joseph Malkevitch,
obviously not $4$-connected: removing $3$ vertices (surrounding one) disconnects.
(A graph is $4$-connected if it requires removal of $4$ vertices to disconnect it.)

* H Whitney. A theorem on graphs. Ann. of Math., 32 (1931), pp. 378–390.

In response to the OP's query: A connected triangulated graph with no Hamiltonian path.

Perhaps the OP may be interested in this paper:

Arkin, Esther M., Martin Held, Joseph SB Mitchell, and Steven S. Skiena. "Hamiltonian triangulations for fast rendering." The Visual Computer. 12, No. 9 (1996): 429-444.
(Springer link.)

• Thank you for the reference! But what about Hamiltonian path? – OHO Jan 17 '16 at 1:16
• I should clarify that by a planar triangulation I mean this: mathworld.wolfram.com/TriangulatedGraph.html The second example is not a planar triangulation. – OHO Jan 17 '16 at 1:59
• The answer is still No, but now you need a maximal planar triangulated graph with at least $8$ "separating triangles." This is easily constructed, and it has no Hamiltonian path. – Joseph O'Rourke Jan 17 '16 at 2:30

See the answer to this question. The magic word is "Kleetope". For more information than you imagined possible, see Guido Helden's Thesis.