On the number of Hamiltonian cycles in triangulations
Jan Kratochvı́l, Dainis Zeps · Journal of Graph Theory · 1988
Abstract It is proved that if a planar triangulation different from K 3 and K 4 contains a Hamiltonian cycle, then it contains at least four of them. Together with the result of Hakimi, Schmeichel, and Thomassen [2], this yields that, for n ⩾ 12, the minimum number of Hamiltonian cycles in a Hamiltonian planar triangulation on n vertices is four. We also show that this theorem holds for triangulations of arbitrary surfaces and for 3‐connected triangulated graphs.