Cubic Planar Hypohamiltonian Graph


Araya and Wiener (2011) found the two cubic planar hypohamiltonian Araya-Wiener graphs on 70 and 88 vertices. McKay and Jooyandeh subsequently found an additional 6 cubic planar hypohamiltonian graphs on 70 vertices (McKay), the first of which was independently rediscovered by Tsai (2024v1). It is known that no such graph exists on 42 or fewer vertices (Aldred et al. 2000, Araya and Wiener 2011). While the smallest possible number of vertices for a cubic planar hypohamiltonian graph is not known, it must lie between 54 and 70 vertices inclusive (Goedgebeur and Zamfirescu 2017, Tsai 2024).

Araya and Wiener (2011) showed that a cubic planar hypohamiltonian graph on 70+4m vertices exists for every nonnegative even integer m. Holton and Sheehan (1993) asked if there exists an integer n such that a cubic planar hypohamiltonian graph exists for every even integer >=n, and Araya and Wiener (2011) settled the question with n=86.

See also

Cubic Graph, Cubic Hypohamiltonian Graph, Hypohamiltonian Graph, Planar Graph, Planar Hypohamiltonian Graph

Explore with Wolfram|Alpha


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.Araya, M. and Wiener, G. "On Cubic Planar Hypohamiltonian and Hypotraceable Graphs." Elec. J. Combin. 18, 2011., J. and Zamfirescu, C. T. "Improved Bounds for Hypohamiltonian Graphs." Ars Math. Contemp. 13, 235-257, 2017.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.", C.-C. "Small Planar Hypohamiltonian Graphs." 8 Apr 2024.

Cite this as:

Weisstein, Eric W. "Cubic Planar Hypohamiltonian Graph." From MathWorld--A Wolfram Web Resource.

Subject classifications