# 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?

-

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.
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 at 2:30