A planar hypohamiltonian graph is a hypohamiltonian graph that is also planar. A number of planar
hypohamiltonian graphs are illustrated above.
Chvátal (1973) first asked if there existed planar hypohamiltonian graphs, and in fact it was conjectured that such graphs might not exist (Grünbaum 1974,
Jooyandeh et al. 2017). An infinite family was subsequently found by Thomassen
(1976), the smallest among them having 105 vertices. The following table summarizes
incrementally smallest known planar hypohamiltonian graphs.
Jooyandeh et al. (2017) searched for "planar 4-face deflatable hypohamiltonian graphs" and found 25 on 40 vertices (all of girth 4), 179 on 42 graphs (including
the Wiener-Araya graph), and 496 on 43 vertices.
They also showed that there exist planar hypohamiltonian graphs of order for every (Jooyandeh et al. 2017), a result subsequently
improved to
(Tsai 2024). It is not known if 34 is the smallest possible vertex count of a planar
hypohamiltonian, with 23 being the best currently known lower bound (Goedgebeur and
Zamfirescu 2017; improving previous bounds from Aldred et al. 1997, Jooyandeh
et al. 2017).
There are no hypohamiltonian planar graphs with girth 5 on fewer than 45 vertices, and there is exactly one such graph on 45 vertices (Jooyandeh et al. 2017),
illustrated above.
Thomassen (1976, 1978) proved that eery planar hypohamiltonian graph contains a vertex of degree 3, and Zamfirescu (2019) proved that every planar hypohamiltonian graph contains at least four cubic vertices (Tsai 2024).
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, 2011. http://www.combinatorics.org/ojs/index.php/eljc/article/view/v18i1p85/.Chvátal,
V. "Flip-Flops in Hypohamiltonian Graphs." Canad. Math. Bull.16,
33-41, 1973.Goedgebeur, J. and Zamfirescu, C. T. "Improved
Bounds for Hypohamiltonian Graphs." Ars Math. Contemp.13, 235-257,
2017.Gruünbaum, B. "Vertices Missed by Longest Paths or Circuits."
J. Combin. Th.17, 31-38, 1974.Holton, D. A. and
Sheehan, J. The
Petersen Graph. Cambridge, England: Cambridge University Press, 1993.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.McKay, B. D. "Plane
Graphs: Hypohamiltonian Planar Graphs." http://users.cecs.anu.edu.au/~bdm/data/planegraphs.html.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. Math14, 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. http://arxiv.org/abs/0904.3012.Wiener,
G. and Araya, M. "On Planar Hypohamiltonian Graphs." J. Graph Th.67,
55-68, 2011.Zamfirescu, C. T. and Zamfirescu, T. I. "A
Planar Hypohamiltonian Graph with 48 Vertices." J. Graph Th.48,
338-342, 2007.Zamfirescu, C. T. "Cubic Vertices in Planar
Hypohamiltonian Graphs." J. Graph Th.90, 189-207, 2019.
for every 
(Jooyandeh et al. 2017), a result subsequently
improved to 
(Tsai 2024). It is not known if 34 is the smallest possible vertex count of a planar
hypohamiltonian, with 23 being the best currently known lower bound (Goedgebeur and
Zamfirescu 2017; improving previous bounds from Aldred et al. 1997, Jooyandeh
et al. 2017).
be the vertex connectivity, 
the minimum vertex
degree, and 
the edge connectivity
of a planar hypohamiltonian graph 
,
