A hypohamiltonian graph is a graph for which is nonhamiltonian,
but
is Hamiltonian for every vertex (Bondy and Murty 1976, p. 61).
The Petersen graph, which has ten vertices,
is the smallest hypohamiltonian graph (Herz et al. 1967; Bondy and Murty 1976,
p. 61) and the only such graph on ten vertices.
Herz et al. (1967) showed that there are no hypohamiltonian graphs
with 11 or 12 vertices.
By parity, no bipartite graph is hypohamiltonian.
Many (but not all) snarks are hypohamiltonian.
Sousselier found a cubic hypohamiltonian graph on 18 vertices (Chvátal 1973). Chvátal (1973) showed there exists a hypohamiltonian graph on vertices for every . More generally, there exists a hypohamiltonian graph
for every
with the exception of (Collier and Schmeichel 1978) and (Aldred et al. 1997). Aldred et al. (1997)
give a complete enumeration of all (seven) hypohamiltonian graphs on 17 or fewer
vertices. McKay lists all hypohamiltonian graphs on fewer
than 18 vertices and a selection of larger examples.
His cubic collection is complete through 26 vertices,
and includes those on 28 vertices with girth
at least 5 and those on 30 vertices with girth
at least 6. The numbers of nonisomorphic hypohamiltonian
graphs on , 2, ... vertices are 0,
0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 1, 0, 1, 4, 0, 14, 34, ... (OEIS A141150;
Goedgebeur and Zamfirescu 2017).
Thomassen (1973) found hypohamiltonian graphs on and 25 vertices, and Collier and Schmeichel (1978) found
"new" hypohamiltonian graphs for and 22, though their "new" graph is actually isomorphic to the first Blanuša
snark and their "new" graphs are isomorphic to the Loupekine
snarks.
A number of non-snark hypohamiltonian graphs, including
a number previously discussed, are shown above, ordered by vertex count.
Aldred, R. E. L.; Bau, S.; Holton, D. A.; and McKay, B. D. "Nonhamiltonian 3-Connected Cubic Planar Graphs."
SIAM J. Disc. Math.13, 25-32, 2000.Aldred, R. E. L.;
McKay, B. D.; and Wormald, N. C. "Small Hypohamiltonian Graphs."
J. Combin. Math. Combin. Comput.23, 143-152, 1997.Araya,
M. and Wiener, G. "On Cubic Planar Hypohamiltonian and Hypotraceable Graphs."
Elec. J. Combin.18, No. 1, P85, 2011. https://doi.org/10.37236/572.Bondy,
J. A. "Variations of the Hamiltonian Theme." Canad. Math. Bull.15,
57-62, 1972.Bondy, J. A. and Murty, U. S. R. Graph
Theory with Applications. New York: North Holland, p. 61, 1976.Chvátal,
V. "Flip-Flops in Hypohamiltonian Graphs." Canad. Math. Bull.16,
33-41, 1973.Collier, J. B. and Schmeichel, E. F. "Systematic
Searches for Hypohamiltonian Graphs." Networks8, 193-200, 1978.Doyen,
J. and van Diest, V. "New Families of Hypohamiltonian Graphs." Disc.
Math.13, 225-236, 1975.Gaudin, T.; Herz, J.-C.; and Rossi,
P. "Solution de problème no. 29." Française Informat.
Recherche Opérationnelle8, 214-218, 1964.Godsil,
C. and Royle, G. Algebraic
Graph Theory. New York: Springer-Verlag, p. 66, 2001.Goedgebeur,
J. and Zamfirescu, C. T. "Improved Bounds for Hypohamiltonian Graphs."
Ars Math. Contemp.13, 235-257, 2017.Grotschel, M. "On
the Monotone Symmetric Travelling Salesman Problem: Hypohamiltonian/Hypotraceable
Graphs and Facets." Math. Operations Res.5, 285-292, 1980.Harary,
F. Graph
Theory. Reading, MA: Addison-Wesley, 1994.Hatzel, H. "Ein
planarer hypohamiltonscher Graph mit 57 Knoten." Math. Ann.243,
213-216, 1979.Herz, J. C.; Duby, J. J.; and Vigué,
F. "Recherche systématique des graphes hypohamiltoniens." In Theory
of Graphs: Internat. Sympos., Rome 1966 (Ed. P. Rosenstiehl). Paris, France:
Gordon and Breach, pp. 153-159, 1967.Holton, D. A. and Sheehan,
J. The
Petersen Graph. Cambridge, England: Cambridge University Press, 1993.House
of Graphs. "Hypohamiltonian Graphs." https://houseofgraphs.org/meta-directory/hypohamiltonian.Jooyandeh,
M.; McKay, B. D.; Östergård, P. R. J.; Pettersson, V. H.;
and Zamfirescu, C. T. "Planar Hypohamiltonian Graphs on 40 Vertices."
J. Graph Th.84, 121-133, 2017.Katerinis, P. "Some
Properties of Hypohamiltonian Graphs." Aeq. Math.72, 139-151,
2006.Lindgren, W. F. "An Infinite Class of Hypohamiltonian
Graphs." Amer. Math. Monthly74, 1087-1089, 1967.McKay,
B. "Hypohamiltonian Graphs." https://users.cecs.anu.edu.au/~bdm/data/graphs.html.Skupień,
Z. "Exponentially Many Hypohamiltonian Snarks." Electronic Notes in
Disc. Meth.28, 417-424, 2007.Sloane, N. J. A.
Sequence A141150 in "The On-Line Encyclopedia
of Integer Sequences."Sousselier, R. "Problème no.
29: Le cercle des irascibles." Rev. Franc. Rech. Operat.7, 405-406,
1963.Thomassen, C. "Hypohamiltonian and Hypotraceable Graphs."
Disc. Math.9, 91-96, 1974.Thomassen, C. "On Hypohamiltonian
Graphs." Disc. Math.10, 383-390, 1974.Thomassen,
C. "Planar and Infinite Hypohamiltonian and Hypotraceable Graphs." Disc.
Math.14, 377-389, 1976.Thomassen, C. "Hypohamiltonian
Graphs and Digraphs." In Theory
and Applications of Graphs Proceedings, Michigan May 11-15, 1976 (Ed. Y. Alavi
and D. R. Lick). New York: Springer-Verlag, pp. 557-571, 1978.Thomassen,
C. "Planar Cubic Hypohamiltonian and Hypotraceable Graphs." J. Comb.
Th. B30, 36-44, 1981.Tsai, C.-C. "Small Planar Hypohamiltonian
Graphs." 8 Apr 2024. https://arxiv.org/abs/2403.18384.Wiener,
G. and Araya, M. "The Ultimate Question." 20 Apr 2009. https://arxiv.org/abs/0904.3012.Wiener,
G. and Araya, M. "On Planar Hypohamiltonian Graphs." J. Graph Th.67,
55-68, 2011.Zamfirescu, C. T. "Cubic Vertices in Planar Hypohamiltonian
Graphs." J. Graph Th.90, 189-207, 2019.Zamfirescu,
C. T. and Zamfirescu, T. I. "A Planar Hypohamiltonian Graph with 48
Vertices." J. Graph Th.48, 338-342, 2007.
for which 
is nonhamiltonian,
but 
is Hamiltonian for every vertex 
(Bondy and Murty 1976, p. 61).
The Petersen graph, which has ten vertices,
is the smallest hypohamiltonian graph (Herz et al. 1967; Bondy and Murty 1976,
p. 61) and the only such graph on ten vertices.
Herz et al. (1967) showed that there are no hypohamiltonian graphs
with 11 or 12 vertices.
vertices constructed independently by Sousselier (in
Herz et al. 1967) and Lindgren (1967).
vertices.
vertices for every 
. More generally, there exists a hypohamiltonian graph
for every 
with the exception of 
(Collier and Schmeichel 1978) and 
(Aldred et al. 1997). Aldred et al. (1997)
give a complete enumeration of all (seven) hypohamiltonian graphs on 17 or fewer
vertices. McKay lists all hypohamiltonian graphs on fewer
than 18 vertices and a selection of larger examples.
His cubic collection is complete through 26 vertices,
and includes those on 28 vertices with girth
at least 5 and those on 30 vertices with girth
at least 6. The numbers of nonisomorphic hypohamiltonian
graphs on 
, 2, ... vertices are 0,
0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 1, 0, 1, 4, 0, 14, 34, ... (OEIS A141150;
Goedgebeur and Zamfirescu 2017).
and 25 vertices, and Collier and Schmeichel (1978) found
"new" hypohamiltonian graphs for 
and 22, though their "new" 
graph is actually isomorphic to the first Blanuša
snark and their "new" 
graphs are isomorphic to the Loupekine
snarks.
