TOPICS
Search

Barnette-Bosák-Lederberg Graph

DOWNLOAD Mathematica NotebookDownload Wolfram Notebook
BarnetteBosakLederbergGraphReadWilsonGruenbaum

The Barnette-Bosák-Lederberg graph is a graph on 38 vertices which is one of the smallest examples of a planar 3-connected cubic nonhamiltonian graph, i.e., a smallest known counterexample to Tait's Hamiltonian graph conjecture. It was discovered by Lederberg (1965), and apparently also by D. Barnette and J. Bosák around the same time. It is illustrated above in two drawings due to Read and Wilson (1998) and Grünbaum (2003, p. 361), respectively, the latter of which shows construction using two Tutte fragments (cf. Holton and McKay 1988). In all, there are exactly six 38-vertex cubic nonhamiltonian polyhedral graphs, all of which can be constructed by splicing in two Tutte fragments at different vertices of a pentagonal prism graph (Holton and McKay 1988).

BarnetteBosakLederbergGraphEmbeddings

A number of other planar graph drawings are illustrated above (E. Weisstein, Jan. 18, 2026).

The Barnette-Bosák-Lederberg graph is implemented in the Wolfram Language as GraphData["BarnetteBosakLederbergGraph"].

Barnette-Bosak-LederbergGraphMatrices

The figures above show the adjacency, incidence, and graph distance matrices of the Barnette-Bosák-Lederberg graph.

The Barnette-Bosák-Lederberg graph is a platypus graph, as are the other five 38-vertex cubic nonhamiltonian polyhedral graphs (Goedgebeur et al. 2020).

See also

Cubic Nonhamiltonian Graph, Tait's Hamiltonian Graph Conjecture

Explore with Wolfram|Alpha

References

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. Fig. 17.1.5 in Convex Polytopes, 2nd ed. New York: Springer-Verlag, p. 361, 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.House of Graphs. "Barnette Bosak Lederberg Graph." https://houseofgraphs.org/graphs/954.Lederberg, J. "DENDRAL-64: A System for Computer Construction, Enumeration and Notation of Organic Molecules as Tree Structures and Cyclic Graphs. Part II. Topology of Cyclic Graphs." Interim Report to the National Aeronautics and Space Administration. Grant NsG 81-60. December 15, 1965. http://profiles.nlm.nih.gov/BB/A/B/I/U/_/bbabiu.pdf.Pegg, E. Jr. "The Icosian Game, Revisited." Mathematica J. 11, 310-314, 2009.Read, R. C. and Wilson, R. J. An Atlas of Graphs. Oxford, England: Oxford University Press, pp. 263 and 274, 1998.Thomassen, C. "Planar Cubic Hypohamiltonian and Hypotraceable Graphs." J. Comb. Th. B 30, 36-44, 1981.

Referenced on Wolfram|Alpha

Barnette-Bosák-Lederberg Graph

Cite this as:

Weisstein, Eric W. "Barnette-Bosák-Lederberg Graph." From MathWorld--A Wolfram Resource. https://mathworld.wolfram.com/Barnette-Bosak-LederbergGraph.html

Subject classifications