On the hamiltonicity of a planar graph and its vertex‐deleted subgraphs
Carol T. Zamfirescu · Journal of Graph Theory · 2022
Abstract 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 ‐vertex graph with minimum degree at least 4 at least vertex‐deleted subgraphs are hamiltonian, then the graph contains two hamiltonian cycles, but that for every there exists a nonhamiltonian polyhedral ‐vertex graph with minimum degree at least 4 containing 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.