The Barnette-Bosák-Lederberg graph is a graph on 38 vertices which is one of smallest example sof a planar 3-connected 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 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"].
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 nonhamiltonian polyhedral graphs (Goedgebeur et al. 2020).
