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 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 following table summarizes some properties of the Barnette-Bosák-Lederberg graph.
| property | value |
| automorphism group order | 2 |
| chromatic number | 3 |
| chromatic polynomial | ? |
| claw-free | no |
| clique number | 2 |
| determined by spectrum | no |
| diameter | 9 |
| distance-regular graph | no |
| edge chromatic number | 3 |
| edge connectivity | 3 |
| edge count | 57 |
| edge transitive | no |
| Eulerian | no |
| face count | 21 |
| graph genus | 0 |
| girth | 4 |
| Hamiltonian | no |
| Hamiltonian path count | ? |
| hypohamiltonian | no |
| hypotraceable | no |
| integral graph | no |
| independence number | 16 |
| line graph | no |
| perfect matching graph | no |
| planar | yes |
| polyhedral graph | yes |
| radius | 5 |
| regular | yes |
| square-free | no |
| symmetric | no |
| traceable | yes |
| triangle-free | yes |
| vertex connectivity | 3 |
| vertex count | 38 |
| vertex transitive | no |
| weakly regular parameters | (38,(3),(0),(0,1,2)) |
