The Barnette-Bosák-Lederberg graph is a graph on 38 vertices which is the smallest known example of a planar 3-connected nonhamiltonian graph, i.e., the 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 following table summarizes some properties of the Barnette-Bosák-Lederberg graph.
|automorphism group order||2|
|determined by spectrum||no|
|edge chromatic number||3|
|Hamiltonian path count||?|
|perfect matching graph||no|
|weakly regular parameters||(38,(3),(0),(0,1,2))|