Tutte 8-Cage

The Tutte 8-cage (Godsil and Royle 2001, p. 59; right figure) is a cubic graph on 30 nodes and 45 edges which is the Levi graph of the Cremona-Richmond configuration. It consists of the union of the two leftmost subgraphs illustrated above. The Tutte 8-cage is the unique -cage graph and Moore graph. It is also a generalized polygon which is the point/line Levi graph of the generalized quadrangle and its line graph is the generalized octagon . The graph was first discovered by Tutte (1947) and is also called the Tutte-Coxeter graph (Bondy and Murty 1976, p. 237; Brouwer et al. 1989, p. 209) or Tutte's cage (Read and Wilson 1998, p. 271).

The Tutte 8-cage is illustrated above in a number of embeddings.

The Tutte 8-cage graph has rectilinear crossing number 13, as established by G. Exoo around 1990 (G. Exoo, pers. comm., May 12, 2019). It is the smallest known cubic graph with graph crossing number of 13, making it likely a smallest cubic crossing number graph, though as of May 2019 this has not yet been definitively established (Pegg and Exoo 2009, Clancy et al. 2019).

It is 4-arc transitive, has girth 8, diameter 4, chromatic number 2, and automorphism group order 1440. It is also distance-regular and distance-transitive with intersection array . The Tutte 8-cage graph is an integral graph with graph spectrum . It can be represented in LCF notation as (Frucht 1976).

It is also a unit-distance graph (Gerbracht 2008), as illustrated above in a number of unit-distance embeddings (E. Gerbracht, pers. comm., Jan. 2010).

The Tutte 8-cage is implemented in the Wolfram Language as GraphData["Tutte8Cage"].