Perihamiltonian Graph
A perihamiltonian is a nonhamiltonian graph for which every edge-contracted subgraph is Hamiltonian.
With the convention that the singleton graph K_1 is considered Hamiltonian, the path graph P_2=K_2 is perihamiltonian since its only edge contraction is K_1.
Equivalently, a nonhamiltonian graph G is perihamiltonian iff, for every edge uv of G, at least one of the vertex-deleted graphs G-u or G-v is Hamiltonian. Every hypohamiltonian graph is perihamiltonian, and every perihamiltonian graph is traceable. For every n>=2, the complete bipartite graph K_(n,n+1) is perihamiltonian (Fabrici et al. 2021).
The numbers of perihamiltonian graphs on n=1, 2, ... vertices are 0, 1, 0, 0, 1, 0, 4, 0, 43, 2, 1730, 25, ... (OEIS A392751; House of Graphs), where the second term counts P_2=K_2.
See also
Almost Hamiltonian Graph, Complete Bipartite Graph, Edge Contraction, Hamiltonian Graph, Hypohamiltonian Graph, Perfectly Hamiltonian Graph, Subhamiltonian Graph, Traceable GraphExplore with Wolfram|Alpha
References
Fabrici, I.; Madaras, T.; Timková, M.; van Cleemput, N.; and Zamfirescu, C. T. "Non-Hamiltonian Graphs in Which Every Edge-Contracted Subgraph Is Hamiltonian." Appl. Math. Comput. 392, Art. 125714, 2021.House of Graphs. "Perihamiltonian Graphs." https://houseofgraphs.org/meta-directory/perihamiltonian.Sloane, N. J. A. Sequence A392751 in "The On-Line Encyclopedia of Integer Sequences."Cite this as:
Weisstein, Eric W. "Perihamiltonian Graph." From MathWorld--A Wolfram Resource. https://mathworld.wolfram.com/PerihamiltonianGraph.html