The Barnette-Bosák-Lederberg graph is a graph on 38 vertices which is one of smallest example sof a planar3-connectednonhamiltonian 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 embeddings due to Read and Wilson (1998) and Grünbaum (2003, p. 361),
respectively, the latter of which shows construction using two Tutte
fragments (c.f. Holton and McKay 1988). In all, there are exactly 38-vertex 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).
A number of other planar emebddings are illustrated above (E. Weisstein, Jan. 18, 2026).
The Barnette-Bosák-Lederberg graph is implemented in the Wolfram
Language as GraphData["BarnetteBosakLederbergGraph"].
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. B45, 305-319,
1988.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. B30, 36-44, 1981.
