Editing Tutte–Coxeter graph (section)

{{Short description|3-regular graph with 30 vertices and 45 edges}}
{{Distinguish|Coxeter graph}}{{infobox graph
 | name = Tutte–Coxeter graph
 | image = [[File:Tutte eight cage.svg|180px]]
 | image_caption =
 | namesake = [[W. T. Tutte]]<br />[[H. S. M. Coxeter]]
 | vertices = 30
 | edges = 45
 | diameter = 4
 | radius = 4
 | automorphisms = 1440 (Aut(S<sub>6</sub>))
 | girth = 8
 | chromatic_number = 2
 | chromatic_index = 3
 | properties = [[Cubic graph|Cubic]]<br />[[Cage (graph theory)|Cage]]<br />[[Moore graph]]<br />[[Symmetric graph|Symmetric]]<br>[[distance-regular graph|Distance-regular]]<br>[[distance-transitive graph|Distance-transitive]]<br />[[Bipartite graph|Bipartite]]
|book thickness=3|queue number=2}}

In the [[mathematics|mathematical]] field of [[graph theory]], the '''Tutte–Coxeter graph''' or '''Tutte eight-cage''' or '''Cremona–Richmond graph''' is a 3-[[regular graph]] with 30 vertices and 45 edges. As the unique smallest [[cubic graph]] of [[girth (graph theory)|girth]] 8, it is a [[cage (graph theory)|cage]] and a [[Moore graph]]. It is [[bipartite graph|bipartite]], and can be constructed as the [[Levi graph]] of the [[generalized quadrangle]] ''W''<sub>2</sub> (known as the [[Cremona–Richmond configuration]]). The graph is named after [[William Thomas Tutte]] and [[H. S. M. Coxeter]]; it was discovered by Tutte (1947) but its connection to geometric configurations was investigated by both authors in a pair of jointly published papers (Tutte 1958; Coxeter 1958a).

All the [[cubic graph|cubic]] [[distance-regular graph]]s are known.<ref>Brouwer, A. E.; Cohen, A. M.; and Neumaier, A. Distance-Regular Graphs. New York: Springer-Verlag, 1989.</ref> The Tutte–Coxeter is one of the 13 such graphs.

It has [[Crossing number (graph theory)|crossing number]] 13,<ref>{{cite journal |last1=Pegg |first1=E. T. |author1-link=Ed Pegg, Jr.|last2=Exoo |first2=G. |title=Crossing Number Graphs |journal=Mathematica Journal |volume=11 |year=2009 |issue=2 |doi=10.3888/tmj.11.2-2|doi-access=free }}</ref><ref>{{cite web |last=Exoo |first=G. |url=http://isu.indstate.edu/ge/COMBIN/RECTILINEAR/ |title=Rectilinear Drawings of Famous Graphs}}</ref> [[book thickness]] 3 and [[queue number]] 2.<ref>Wolz, Jessica; ''Engineering Linear Layouts with SAT.'' Master Thesis, University of Tübingen, 2018</ref>