Vertex degrees and 2-cuts in graphs with many hamiltonian vertex-deleted subgraphs

Abstract A 2-connected non-hamiltonian graph G is a k-graph if for exactly k | V ( G ) | vertices in G, removing such a vertex yields a non-hamiltonian graph. We characterise k-graphs of connectivity 2 and describe structurally interesting examples of such graphs containing no cubic vertex or of minimum degree at least 4, with a special emphasis on the planar case. We prove that there exists a k 0 such that for every k ≥ k 0 infinitely many planar k-graphs of connectivity 2 and minimum degree 4 exist. As a variation of a result of Thomassen, we show that certain planar 3-graphs must contain a cubic vertex.