TOPICS
Perihamiltonian Graph
A perihamiltonian is a nonhamiltonian graph for which every edge-contracted subgraph is Hamiltonian.
With the convention that the singleton graph 
is considered Hamiltonian,
the path graph 
is perihamiltonian since its only edge contraction is
.
Equivalently, a nonhamiltonian graph 
is perihamiltonian iff,
for every edge 
of 
,
at least one of the vertex-deleted graphs 
or 
is Hamiltonian. Every
hypohamiltonian graph is perihamiltonian,
and every perihamiltonian graph is traceable.
For every 
,
the complete bipartite graph 
is perihamiltonian (Fabrici et al. 2021).
The numbers of perihamiltonian graphs on 
, 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 
.
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