In the

mathematical Mathematics is an area of knowledge that includes the topics of numbers, formulas and related structures, shapes and the spaces in which they are contained, and quantities and their changes. These topics are represented in modern mathematics ...

field of

graph theory In mathematics, graph theory is the study of ''graphs'', which are mathematical structures used to model pairwise relations between objects. A graph in this context is made up of '' vertices'' (also called ''nodes'' or ''points'') which are conne ...

, the Tutte–Coxeter graph or Tutte eight-cage or Cremona–Richmond graph is a 3-

regular graph In graph theory, a regular graph is a graph where each vertex has the same number of neighbors; i.e. every vertex has the same degree or valency. A regular directed graph must also satisfy the stronger condition that the indegree and outdegree o ...

with 30 vertices and 45 edges. As the unique smallest

cubic graph In the mathematical field of graph theory, a cubic graph is a graph in which all vertices have degree three. In other words, a cubic graph is a 3-regular graph. Cubic graphs are also called trivalent graphs. A bicubic graph is a cubic bipa ...

girth Girth may refer to: ;Mathematics * Girth (functional analysis), the length of the shortest centrally symmetric simple closed curve on the unit sphere of a Banach space * Girth (geometry), the perimeter of a parallel projection of a shape * Girth ...

8, it is a

cage A cage is an enclosure often made of mesh, bars, or wires, used to confine, contain or protect something or someone. A cage can serve many purposes, including keeping an animal or person in captivity, capturing an animal or person, and displayin ...

and a

Moore graph In graph theory, a Moore graph is a regular graph whose girth (the shortest cycle length) is more than twice its diameter (the distance between the farthest two vertices). If the degree of such a graph is and its diameter is , its girth must e ...

. It is bipartite, and can be constructed as the

Levi graph In combinatorial mathematics, a Levi graph or incidence graph is a bipartite graph associated with an incidence structure.. See in particulap. 181 From a collection of points and lines in an incidence geometry or a projective configuration, we form ...

of the

generalized quadrangle In geometry, a generalized quadrangle is an incidence structure whose main feature is the lack of any triangles (yet containing many quadrangles). A generalized quadrangle is by definition a polar space of rank two. They are the with ''n'' = 4 ...

''W''₂ (known as the

Cremona–Richmond configuration In mathematics, the Cremona–Richmond configuration is a configuration of 15 lines and 15 points, having 3 points on each line and 3 lines through each point, and containing no triangles. It was studied by and . It is a generalized quadrangle wit ...

). The graph is named after

William Thomas Tutte William Thomas Tutte OC FRS FRSC (; 14 May 1917 – 2 May 2002) was an English and Canadian codebreaker and mathematician. During the Second World War, he made a brilliant and fundamental advance in cryptanalysis of the Lorenz cipher, a majo ...

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

distance-regular graph In the mathematical field of graph theory, a distance-regular graph is a regular graph such that for any two vertices and , the number of vertices at distance from and at distance from depends only upon , , and the distance between and . ...

s are known. The Tutte–Coxeter is one of the 13 such graphs. It has crossing number 13,

book thickness In graph theory, a book embedding is a generalization of planar embedding of a graph to embeddings into a ''book'', a collection of half-planes all having the same line as their boundary. Usually, the vertices of the graph are required to lie ...

3 and

queue number In the mathematical field of graph theory, the queue number of a graph is a graph invariant defined analogously to stack number (book thickness) using first-in first-out (queue) orderings in place of last-in first-out (stack) orderings. Defi ...

2.Wolz, Jessica; ''Engineering Linear Layouts with SAT.'' Master Thesis, University of Tübingen, 2018

Constructions and automorphisms

A particularly simple combinatorial construction of the Tutte–Coxeter graph is due to Coxeter (1958b), based on work by Sylvester (1844). In modern terminology, take a

complete graph In the mathematical field of graph theory, a complete graph is a simple undirected graph in which every pair of distinct vertices is connected by a unique edge. A complete digraph is a directed graph in which every pair of distinct vertices is c ...

on 6 vertices ''K''₆. It has 15 edges and also 15

perfect matching In graph theory, a perfect matching in a graph is a matching that covers every vertex of the graph. More formally, given a graph , a perfect matching in is a subset of edge set , such that every vertex in the vertex set is adjacent to exactly ...

s. Each vertex of the Tutte–Coxeter graph corresponds to an edge or perfect matching of the ''K''₆, and each edge of the Tutte–Coxeter graph connects a perfect matching of the ''K''₆ to each of its three component edges. By symmetry, each edge of the ''K''₆ belongs to three perfect matchings. Incidentally, this partitioning of vertices into edge-vertices and matching-vertices shows that the Tutte-Coxeter graph is bipartite. Based on this construction, Coxeter showed that the Tutte–Coxeter graph is a

symmetric graph In the mathematical field of graph theory, a graph is symmetric (or arc-transitive) if, given any two pairs of adjacent vertices and of , there is an automorphism :f : V(G) \rightarrow V(G) such that :f(u_1) = u_2 and f(v_1) = v_2. In oth ...

; it has a

group A group is a number of persons or things that are located, gathered, or classed together. Groups of people * Cultural group, a group whose members share the same cultural identity * Ethnic group, a group whose members share the same ethnic ide ...

of 1440

automorphisms In mathematics, an automorphism is an isomorphism from a mathematical object to itself. It is, in some sense, a symmetry of the object, and a way of mapping the object to itself while preserving all of its structure. The set of all automorphisms ...

, which may be identified with the automorphisms of the group of permutations on six elements (Coxeter 1958b). The

inner automorphism In abstract algebra an inner automorphism is an automorphism of a group, ring, or algebra given by the conjugation action of a fixed element, called the ''conjugating element''. They can be realized via simple operations from within the group it ...

s of this group correspond to permuting the six vertices of the ''K''₆ 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 In mathematics, the outer automorphism group of a group, , is the quotient, , where is the automorphism group of and ) is the subgroup consisting of inner automorphisms. The outer automorphism group is usually denoted . If is trivial and has a t ...

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 spherical building associated to the symplectic group

Sp_4(\mathbb_)

(there is an exceptional isomorphism between this group and the symmetric group

S_6

). More specifically, it is the incidence graph of a

. Concretely, the Tutte-Coxeter graph can be defined from a 4-dimensional

symplectic vector space In mathematics, a symplectic vector space is a vector space ''V'' over a field ''F'' (for example the real numbers R) equipped with a symplectic bilinear form. A symplectic bilinear form is a mapping that is ; Bilinear: Linear in each argument ...

V

over

\mathbb_

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

W\subset V

if and only if

v \in W

Gallery

File:Tutte-Coxeter graph 2COL.svg , The

chromatic number In graph theory, graph coloring is a special case of graph labeling; it is an assignment of labels traditionally called "colors" to elements of a graph subject to certain constraints. In its simplest form, it is a way of coloring the vertices o ...

of the Tutte–Coxeter graph is 2. File:Tutte-Coxeter graph 3color edge.svg, The

chromatic index In graph theory, an edge coloring of a graph is an assignment of "colors" to the edges of the graph so that no two incident edges have the same color. For example, the figure to the right shows an edge coloring of a graph by the colors red, blue ...

of the Tutte–Coxeter graph is 3.

References

* * * * *

External links

* * * Exoo, G. "Rectilinear Drawings of Famous Graphs.

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