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
The Tutte 8-cage graph is an integral graph with
graph spectrum . It can be represented in LCF
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"].
See alsoCage Graph
, Integral Graph
, Smallest Cubic Crossing
, Tutte 12-Cage
Explore with Wolfram|Alpha
ReferencesBondy, J. A. and Murty, U. S. R. Graph Theory with Applications. New York: North Holland, pp. 237 and 276,
1976.Brouwer, A. E.; Cohen, A. M.; and Neumaier, A. Distance
Regular Graphs. New York: Springer-Verlag, p. 209, 1989.Clancy,
K.; Haythorpe, M.; Newcombe, A.; and Pegg, E. Jr. "There Are No Cubic Graphs
on 26 Vertices with Crossing Number 10 or 11." Preprint. 2019.Coxeter,
H. S. M. "Self-Dual Configurations and Regular Graphs." Bull.
Amer. Math. Soc. 56, 413-455, 1950.Coxeter, H. S. M.
"The Chords of the Non-Ruled Quadratic in PG(3,3)." Canad. J. Math. 10,
484-488, 1958.Coxeter, H. S. M. "Twelve Points in PG(5,3)
with 95040 Self-Transformations." Proc. Roy. Soc. London Ser. A 247,
279-293, 1958.DistanceRegular.org. "Tutte's 8-Cage." http://www.distanceregular.org/graphs/tutte8.html.Exoo,
G. "Rectilinear Drawings of Famous Graphs: The Tutte 8-Cage." http://isu.indstate.edu/ge/COMBIN/RECTILINEAR/tutte.gif.Frucht,
R. "A Canonical Representation of Trivalent Hamiltonian Graphs." J.
Graph Th. 1, 45-60, 1976.Gerbracht, E. H.-A. "On
the Unit Distance Embeddability of Connected Cubic Symmetric Graphs." Kolloquium
über Kombinatorik. Magdeburg, Germany. Nov. 15, 2008.Godsil,
C. and Royle, G. Algebraic
Graph Theory. New York: Springer-Verlag, 2001.Harary, F. Graph
Theory. Reading, MA: Addison-Wesley, pp. 174-175, 1994.Pegg,
E. Jr. and Exoo, G. "Crossing Number Graphs." Mathematica J. 11,
161-170, 2009. https://www.mathematica-journal.com/data/uploads/2009/11/CrossingNumberGraphs.pdf.Pisanski,
T. and Randić, M. "Bridges between Geometry and Graph Theory." In
at Work: A Collection of Papers Showing Applications of Geometry (Ed. C. A. Gorini).
Washington, DC: Math. Assoc. Amer., pp. 174-194, 2000.Read, R. C.
and Wilson, R. J. An
Atlas of Graphs. Oxford, England: Oxford University Press, p. 271, 1998.Royle, G. "F030A."
http://www.csse.uwa.edu.au/~gordon/foster/F030A.htmlRoyle, G. "Cubic
W. T. "A Family of Cubical Graphs." Proc. Cambridge Philos. Soc.,
459-474, 1947.Tutte, W. T. Connectivity
in Graphs. Toronto, Ontario: University of Toronto Press, 1966.Tutte,
W. T. "The Chords of the Non-Ruled Quadratic in PG(3,3)." Canad.
J. Math. 10, 481-483, 1958.Wong, P. K. "Cages--A
Survey." J. Graph Th. 6, 1-22, 1982.
Cite this as:
Weisstein, Eric W. "Tutte 8-Cage." From
MathWorld--A Wolfram Web Resource. https://mathworld.wolfram.com/Tutte8-Cage.html