We show that in 5-connected planar and projective planar triangulations on n vertices, the number of Hamiltonian cycles grows exponentially with n. The result is best possible in the sense that 4-connected triangulations on n vertices on any fixed surface may have only polynomially many cycles. Also, there is an infinite class of 5-connected graphs (not on a fixed surface) which have only polynomially many cycles. The result also extends to 5-connected triangulations of the torus if a long standing conjecture of Nash-Williams holds. For any fixed surface, we show that every 5-connected triangulation of large face-width on that surface contains exponentially many cycles.
- Triangulation of a surface
- Planar triangulation
- Projective planar triangulation