K₂-hamiltonian graphs: I

Motivated by a conjecture of Gr\" unbaum and a problem of Katona, Kostochka, Pach, and Stechkin, both dealing with non-Hamiltonian n-vertex graphs and their (n - 2)-cycles, we investigate K₂-Hamiltonian graphs, i.e., graphs in which the removal of any pair of adjacent vertices yields a Hamiltonian graph. In this first part, we prove structural properties and show that there exist infinitely many cubic non-Hamiltonian K₂-Hamiltonian graphs, both of the 3-edge-colorable and the non-3-edge-colorable variety. In fact, cubic K₂-Hamiltonian graphs with chromatic index 4 (such as Petersen's graph) are a subset of the critical snarks. On the other hand, it is proven that non-Hamiltonian K₂-Hamiltonian graphs of any maximum degree exist. Several operations conserving K₂-Hamiltonicity are described, one of which leads to the result that there exists an infinite family of non-Hamiltonian K₂-Hamiltonian graphs in which, asymptotically, a quarter of vertices has the property that removing such a vertex yields a non-Hamiltonian graph. We extend a celebrated result of Tutte by showing that every planar K₂-Hamiltonian graph with minimum degree at least 4 is Hamiltonian. Finally, we investigate K₂-traceable graphs and discuss open problems.