In the mathematical

Mathematics

Mathematics is the study of quantity, space, structure, and change. Mathematicians seek out patterns and formulate new conjectures. Mathematicians resolve the truth or falsity of conjectures by mathematical proofs, which are arguments sufficient to convince other mathematicians of their validity...

 field of graph theory

Graph theory

In mathematics and computer science, graph theory is the study of graphs, mathematical structures used to model pairwise relations between objects from a certain collection. A "graph" in this context refers to a collection of vertices or 'nodes' and a collection of edges that connect pairs of...

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

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 of each vertex are equal to each other...

 with 30 vertices and 45 edges. As the unique smallest cubic graph

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

 of girth 8 it is a cage

Cage (graph theory)

In the mathematical area of graph theory, a cage is a regular graph that has as few vertices as possible for its girth.Formally, an -graph is defined to be a graph in which each vertex has exactly r neighbors, and in which the shortest cycle has length exactly g. It is known that an -graph exists...

 and a Moore graph. It is bipartite

Bipartite graph

In the mathematical field of graph theory, a bipartite graph is a graph whose vertices can be divided into two disjoint sets U and V such that every edge connects a vertex in U to one in V; that is, U and V are independent sets...

, and can be constructed as the Levi graph

Levi graph

In combinatorial mathematics, a Levi graph or incidence graph is a bipartite graph associated with an incidence structure. From a collection of points and lines in an incidence geometry or a projective configuration, we form a graph with one vertex per point, one vertex per line, and an edge for...

 of the generalized quadrangle

Generalized quadrangle

A generalized quadrangle is an incidence structure. A generalized quadrangle is by definition a polar space of rank two. They are the generalized n-gons with n=4...

 W₂. 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

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

 distance-regular graph

Distance-regular graph

In mathematics, a distance-regular graph is a regular graph such that for any two vertices v and w at distance i the number of vertices adjacent to w and at distance j from v is the same. Every distance-transitive graph is distance-regular...

s are known. The Tutte–Coxeter is one of the 13 such graphs.

Duads, synthemes, and automorphisms

A particularly simple combinatorial construction of the Tutte-Coxeter graph is due to Coxeter (1958b), based on much earlier work by Sylvester (1844). From a set of six elements (for instance the letters a,b,c,d,e,f) Sylvester defined a duad to be one of the 15 unordered pairs of elements: ab, ac, ad, ae, af, bc, bd, be, bf, cd, ce, cf, de, df, or ef. He also defined a syntheme to be one of the 15 partitions of the elements into three duads: (ab,cd,ef), (ab,ce,df), etc. Each syntheme contains three duads, and each duad belongs to three synthemes. The Tutte-Coxeter graph can be viewed as having one vertex per duad, one vertex per syntheme, and an edge connecting each syntheme to each of the three duads that form it.

Based on this construction, Coxeter showed that the Tutte–Coxeter graph is a symmetric graph

Symmetric graph

In the mathematical field of graph theory, a graph G is symmetric if, given any two pairs of adjacent vertices u1—v1 and u2—v2 of G, there is an automorphismsuch that...

; it has a group

Group (mathematics)

In mathematics, a group is an algebraic structure consisting of a set together with an operation that combines any two of its elements to form a third element. To qualify as a group, the set and the operation must satisfy a few conditions called group axioms, namely closure, associativity, identity...

 of 1440 automorphisms

Graph automorphism

In the mathematical field of graph theory, an automorphism of a graph is a form of symmetry in which the graph is mapped onto itself while preserving the edge–vertex connectivity....

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

Inner automorphism

In abstract algebra an inner automorphism is a functionwhich, informally, involves a certain operation being applied, then another one performed, and then the initial operation being reversed...

s of this group correspond to permuting the six elements from which we defined the morphemes and synthemes; 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.

External links

• Exoo, G. "Rectilinear Drawings of Famous Graphs." http://isu.indstate.edu/ge/COMBIN/RECTILINEAR/