On the hamiltonicity of a planar graph and its vertex‐deleted subgraphs.

Tutte proved that every planar 4‐connected graph is hamiltonian. Thomassen showed that the same conclusion holds for the superclass of planar graphs with minimum degree at least 4 in which all vertex‐deleted subgraphs are hamiltonian. We here prove that if in a planar n $n$‐vertex graph with minimum degree at least 4 at least n−5 $n-5$ vertex‐deleted subgraphs are hamiltonian, then the graph contains two hamiltonian cycles, but that for every c<1 $c\lt 1$ there exists a nonhamiltonian polyhedral n $n$‐vertex graph with minimum degree at least 4 containing cn $cn$ hamiltonian vertex‐deleted subgraphs. Furthermore, we study the hamiltonicity of planar triangulations and their vertex‐deleted subgraphs as well as Bondy's meta‐conjecture, and prove that a polyhedral graph with minimum degree at least 4 in which all vertex‐deleted subgraphs are traceable, must itself be traceable. [ABSTRACT FROM AUTHOR]