Tutte–Coxeter graph
Tutte–Coxeter graph  

Named after  W. T. Tutte H. S. M. Coxeter 
Vertices  30 
Edges  45 
Radius  4 
Diameter  4 
Girth  8 
Automorphisms  1440 (Aut(S_{6})) 
Chromatic number  2 
Chromatic index  3 
Book thickness  3 
Queue number  2 
Properties  Cubic Cage Moore graph Symmetric Distanceregular Distancetransitive Bipartite 
Table of graphs and parameters 
In the mathematical field of graph theory, the Tutte–Coxeter graph or Tutte eightcage or Cremona–Richmond graph is a 3regular graph with 30 vertices and 45 edges. As the unique smallest cubic graph of girth 8, it is a cage and a Moore graph. It is bipartite, and can be constructed as the Levi graph of the generalized quadrangle W_{2} (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 distanceregular graphs are known.^{[1]} The Tutte–Coxeter is one of the 13 such graphs.
It has crossing number 13,^{[2]}^{[3]} book thickness 3 and queue number 2.^{[4]}
Constructions and automorphisms
[edit]The Tutte–Coxeter graph is the bipartite Levi graph connecting the 15 perfect matchings of a 6vertex complete graph K_{6} 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 of 1440 automorphisms, which may be identified with the automorphisms of the group of permutations on six elements (Coxeter 1958b). The inner automorphisms of this group correspond to permuting the six vertices of the K_{6} 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 automorphisms 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
[edit]This graph is the spherical building associated to the symplectic group (there is an exceptional isomorphism between this group and the symmetric group ). More specifically, it is the incidence graph of a generalized quadrangle.
Concretely, the TutteCoxeter graph can be defined from a 4dimensional symplectic vector space over as follows:
 vertices are either nonzero vectors, or isotropic 2dimensional subspaces,
 there is an edge between a nonzero vector v and an isotropic 2dimensional subspace if and only if .
Gallery
[edit]
The chromatic number of the Tutte–Coxeter graph is 2.

The chromatic index of the Tutte–Coxeter graph is 3.
References
[edit] ^ Brouwer, A. E.; Cohen, A. M.; and Neumaier, A. DistanceRegular Graphs. New York: SpringerVerlag, 1989.
 ^ Pegg, E. T.; Exoo, G. (2009). "Crossing Number Graphs". Mathematica Journal. 11 (2). doi:10.3888/tmj.11.22.
 ^ Exoo, G. "Rectilinear Drawings of Famous Graphs".
 ^ Wolz, Jessica; Engineering Linear Layouts with SAT. Master Thesis, University of Tübingen, 2018
 Coxeter, H. S. M. (1958a). "The chords of the nonruled quadric in PG(3,3)". Can. J. Math. 10: 484–488. doi:10.4153/CJM19580470.
 Coxeter, H. S. M. (1958b). "Twelve points in PG(5,3) with 95040 selftransformations". Proceedings of the Royal Society A. 247 (1250): 279–293. Bibcode:1958RSPSA.247..279C. doi:10.1098/rspa.1958.0184. JSTOR 100667. S2CID 121676627.
 Sylvester, J. J. (1844). "Elementary researches in the analysis of combinatorial aggregation". Phil. Mag. Series 3. 24: 285–295. doi:10.1080/14786444408644856.
 Tutte, W. T. (1947). "A family of cubical graphs". Proc. Cambridge Philos. Soc. 43 (4): 459–474. Bibcode:1947PCPS...43..459T. doi:10.1017/S0305004100023720. S2CID 123505185.
 Tutte, W. T. (1958). "The chords of the nonruled quadric in PG(3,3)". Can. J. Math. 10: 481–483. doi:10.4153/CJM19580463.
External links
[edit] François Labelle. "3D Model of Tutte's 8cage".
 Weisstein, Eric W. "Levi Graph". MathWorld.
 Exoo, G. "Rectilinear Drawings of Famous Graphs." [1]