TOPICS
Search

Cubic Nonhamiltonian Graph

NonhamiltonianCubicGraphs

Cubic nonhamiltonian graphs are nonhamiltonian graphs that are also cubic. The numbers of nonisomorphic connected cubic nonhamiltonian graphs on n=10, 12, ... nodes are 2, 5, 35, 219, 1666, ... (OEIS A164919). The figure above shows some connected cubic nonhamiltonian graphs that are not snarks (which are excluded since snarks are necessarily both nonplanar and nonhamiltonian).

TaitsHamiltonianGraphConjecture

Cubic nonhamiltonian graphs are of special interest because of Tait's Hamiltonian graph conjecture. The nonhamiltonian cubic polyhedral graphs illustrated above all provide counterexamples to this conjecture. The smallest possible nonhamiltonian cubic polyhedral graph occurs on 38 nodes. In fact there are exactly six such graphs (Holton and McKay 1988), with the Barnette-Bosák-Lederberg graph being the first discovered. There exists a nonhamiltonian cubic polyhedral graph on n nodes for every even n>=38 (Holton and McKay 1988, van Cleemput and Zamfirescu 2018).

The Horton graphs and Ellingham-Horton graphs are examples of 3-connected bicubic graphs that provide counterexamples to the Tutte bicubic graph conjecture.

Hunter (1962) conjectured that all cyclically 5-connected polyhedral graphs contain a Hamiltonian cycle (Grünbaum 2003, p. 365), but a 162-vertex graph due to Walther (1965) provided a counterexample (Grünbaum 2003, pp. 365-366).

The minimum vertex count of an untraceable cubic polyhedral graph is at least 54 (Knorr 2010) and at most 88 (Zamfirescu 1980, Abrishami et al. 2026). There exists such a graph on every even number n>=88 of vertices (van Cleemput and Zamfirescu 2018).

All six smallest cubic nonhamiltonian polyhedral graphs are platypus graphs (Goedgebeur et al. 2020).

See also

Barnette-Bosák-Lederberg graph, Bicubic Nonhamiltonian Graph, Cubic Graph, Horton Graphs, Nonhamiltonian Graph, Quartic Nonhamiltonian Graph, Quintic Nonhamiltonian Graph, Snark, Tait's Hamiltonian Graph Conjecture, Tutte Bicubic Graph Conjecture, Walther Graphs

Explore with Wolfram|Alpha

References

Abrishami, G.; Rahbarnia, F.; and Van Cleemput, N. "On Non-Traceable 3-Connected Planar Cubic Graphs of Minimum Order." Disc. Math. 349, 114983, 2026. https://doi.org/10.1016/j.disc.2026.114983.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.Goedgebeur, J.; Neyt, A.; and Zamfirescu, C. T. "Structural and Computational Results on Platypus Graphs." Appl. Math. Comput., 386:125491, 10 pages, 2020.Grünbaum, B. Convex Polytopes, 2nd ed. New York: Springer-Verlag, 2003.Holton, D. A. and McKay, B. D. "The Smallest Non-Hamiltonian 3-Connected Cubic Planar Graphs Have 38 Vertices." J. Combin. Th. Ser. B 45, 305-319, 1988.Hunter, H. F. "On Non-Hamiltonian Maps and Their Duals." PhD thesis. Troy, NY: Rensselaer Polytechnic Institute, 1962.Knorr, P. "Aufspannende Kreise und Wege in polytopalen Graphen." PhD thesis. Dortmund, Germany: Universität Dortmund, 2010.Sloane, N. J. A. Sequence A164919 in "The On-Line Encyclopedia of Integer Sequences."van Cleemput, N. and Zamfirescu, C. T. "Regular Non-Hamiltonian Polyhedral Graphs." Appl. Math. Comput. 338, 192-206, 2018. https://doi.org/10.1016/j.amc.2018.05.062.Walther, H. "Ein kubischer, planarer, zyklisch fünffach zusammenhängender Graf, der keinen Hamiltonkreis besizt." Wiss. Z. Hochschule Elektrotech. Ilmenau 11, 163-166, 1965.Zamfirescu, T. "Three Small Cubic Graphs with Interesting Hamiltonian Properties." J. Graph Th. 4, 287-292, 1980.

Referenced on Wolfram|Alpha

Cubic Nonhamiltonian Graph

Cite this as:

Weisstein, Eric W. "Cubic Nonhamiltonian Graph." From MathWorld--A Wolfram Resource. https://mathworld.wolfram.com/CubicNonhamiltonianGraph.html

Subject classifications