Editing Tutte–Coxeter graph

{{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>

== Constructions and automorphisms ==
The Tutte–Coxeter graph is the [[bipartite graph|bipartite]] [[Levi graph]] connecting the 15 [[perfect matching]]s of a 6-vertex [[complete graph]] K<sub>6</sub> to its 15 edges, as described by Coxeter (1958b), based on work by Sylvester (1844). Each vertex corresponds to an edge or a perfect matching, and connected vertices represent the [[incidence structure]] between edges and matchings.

Based on this construction, Coxeter showed that the Tutte–Coxeter graph is a [[symmetric graph]]; it has a [[group (mathematics)|group]] of 1440 [[graph automorphism|automorphisms]], which may be identified with the automorphisms of the group of permutations on six elements (Coxeter 1958b). The [[inner automorphism]]s of this group correspond to permuting the six vertices of the ''K''<sub>6</sub> graph; these permutations act on the Tutte–Coxeter graph by permuting the vertices on each side of its bipartition while keeping each of the two sides fixed as a set. In addition, the [[outer automorphism]]s of the group of permutations swap one side of the bipartition for the other. As Coxeter showed, any path of up to five edges in the Tutte–Coxeter graph is equivalent to any other such path by one such automorphism.

== The Tutte–Coxeter graph as a building ==

This graph is the [[Building (mathematics)#Spherical building|spherical building]] associated to the symplectic group <math>Sp_4(\mathbb{F}_{2})</math> (there is an exceptional isomorphism between this group and the symmetric group <math>S_6</math>).  More specifically, it is the incidence graph of a [[generalized quadrangle]].

Concretely, the Tutte-Coxeter graph can be defined from a 4-dimensional [[symplectic vector space]] <math>V</math> over <math>\mathbb{F}_{2}</math> as follows:
* vertices are either nonzero vectors, or isotropic 2-dimensional subspaces,
* there is an edge between a nonzero vector ''v'' and an isotropic 2-dimensional subspace <math>W\subset V</math> if and only if <math>v \in W</math>.

==Gallery==
<gallery>
File:Tutte-Coxeter graph 2COL.svg |The [[chromatic number]] of the Tutte–Coxeter graph is 2.
File:Tutte-Coxeter graph 3color edge.svg|The [[chromatic index]] of the Tutte–Coxeter graph is 3.
</gallery>

== References ==
{{reflist}}
* {{cite journal
 | author = Coxeter, H. S. M.
 | authorlink = H. S. M. Coxeter
 | title = The chords of the non-ruled quadric in PG(3,3)
 | journal = Can. J. Math.
 | volume = 10
 | year = 1958a
 | pages = 484–488
 | doi = 10.4153/CJM-1958-047-0| doi-access = free
 }}
* {{cite journal
 | author = Coxeter, H. S. M.
 | authorlink = H. S. M. Coxeter
 | title = Twelve points in PG(5,3) with 95040 self-transformations
 | journal = [[Proceedings of the Royal Society A]]
 | volume = 247
 | year = 1958b
 | issue = 1250
 | pages = 279–293
 | jstor = 100667
 | doi = 10.1098/rspa.1958.0184| bibcode = 1958RSPSA.247..279C
 | s2cid = 121676627
 }}
* {{cite journal
 | author = Sylvester, J. J.
 | authorlink = J. J. Sylvester
 | title = Elementary researches in the analysis of combinatorial aggregation
 | journal = Phil. Mag.
 | series = Series 3
 | volume = 24
 | year = 1844
 | pages = 285–295
 | doi = 10.1080/14786444408644856| url = https://zenodo.org/record/1431037
 }}
* {{cite journal
 | author = Tutte, W. T.
 | authorlink = William Thomas Tutte
 | title = A family of cubical graphs
 | journal = Proc. Cambridge Philos. Soc.
 | volume = 43
 | year = 1947
 | pages = 459–474
 | doi = 10.1017/S0305004100023720
 | issue = 4| bibcode = 1947PCPS...43..459T
 | s2cid = 123505185
 }}
* {{cite journal
 | author = Tutte, W. T.
 | authorlink = William Thomas Tutte
 | title = The chords of the non-ruled quadric in PG(3,3)
 | journal = Can. J. Math.
 | volume = 10
 | year = 1958
 | pages = 481–483
 | doi = 10.4153/CJM-1958-046-3| doi-access = free
 }}

==External links==
* {{cite web | author = François Labelle | title = 3D Model of Tutte's 8-cage | url = http://www.cs.berkeley.edu/~flab/proto/report/report.html}}
* {{MathWorld|urlname=LeviGraph|title=Levi Graph}}
* Exoo, G. "Rectilinear Drawings of Famous Graphs." [http://isu.indstate.edu/ge/COMBIN/RECTILINEAR/]

{{DEFAULTSORT:Tutte-Coxeter graph}}
[[Category:1958 introductions]]
[[Category:Individual graphs]]
[[Category:Configurations (geometry)]]
[[Category:Regular graphs]]