Coxeter graph

Dots and lines make a special shape.

This shape is named for a man. He was named Coxeter.

There are 28 dots in the shape. Each dot has three lines.

There are 42 lines in all. The shape is very neat. It is also very balanced.

Lines can cross in this shape. It has 11 crossings.

It is a special pattern to study.

Dots and lines can make a special pattern. In math, we call these patterns graphs.

One special pattern is the Coxeter graph. It is named after a man named Coxeter. This graph has 28 dots, called vertices. It also has 42 lines, called edges.

Every dot in this graph is the same. Each dot has exactly three lines joined to it. This makes it a 3-regular graph. The graph is also very balanced. It is a symmetric graph. This means you can move any dot to any other dot. The shape will still look the same.

This graph has a strange rule. It does not have a Hamiltonian cycle. A Hamiltonian cycle is a path that visits every dot once and returns to the start. However, if you remove just one dot, the new shape does have that path.

Lines can cross in this shape. It has 11 crossings. It is the smallest graph of its kind with that many crossings.

Math uses dots and lines to build patterns called graphs. One very special pattern is the Coxeter graph. It is a 3-regular graph. This means every dot, or vertex, has exactly three lines, or edges, joined to it.

This graph has 28 vertices and 42 edges. It is a very balanced shape. Mathematicians call this a symmetric graph. This means you can move any vertex to any other vertex. The shape will still look exactly the same.

This graph has some very strange rules. It does not have a Hamiltonian cycle. A Hamiltonian cycle is a path that visits every dot once and returns home.

However, if you remove just one vertex, the new shape does have that path. This special trait is called being hypohamiltonian. It is also a 1-planar graph. This means the lines can be drawn so they do not overlap too much.

The graph has a rectilinear crossing number of 11. This is the smallest cubic graph with that many crossings.

We can build this graph in a few different ways. One way uses something called a Fano plane. You take 35 groups of three objects. Then you take away 7 specific groups. This leaves you with 28 groups to use as vertices.

You can also build it from the Heawood graph. You make a vertex for every 6-cycle in that graph. Another way uses the Hoffman-Singleton graph. You pick one vertex and its neighbors. Then you remove those and keep the rest.

This graph is named after Harold Scott MacDonald Coxeter. He was a mathematician who studied these kinds of shapes. The graph is also part of a special list. The Foster census calls it F28A. It is the only cubic symmetric graph with 28 vertices.

It is also one of 13 known cubic distance-regular graphs. This means the distances between dots follow a very strict pattern. Scientists use math to find these unique structures. They help us understand how complex shapes can work.

Think about a map of many cities and roads. Each city is a vertex and each road is an edge. The Coxeter graph is like a very organized map. It has a chromatic number of 3. This means you can color the dots with three colors.

No two dots connected by a line will have the same color. You can also think about it as a puzzle. It is a shape that almost follows one rule, but not quite. This makes it a great example for math students to study.

In the field of graph theory, mathematicians study structures made of points and lines. One highly unique structure is the Coxeter graph. It is a 3-regular graph, which means every single vertex has exactly three edges connected to it. This specific graph contains 28 vertices and 42 edges. It is also classified as one of the 13 known cubic distance-regular graphs.

This classification means the distances between its vertices follow a very strict and predictable pattern.

The Coxeter graph possesses several complex mathematical properties. It has a chromatic number of 3 and a chromatic index of 3. This means you can color the vertices so that no two connected vertices share a color using only three colors.

Its girth is 7, which is the length of its shortest cycle. The graph also has a radius of 4 and a diameter of 4. It is both 3-vertex-connected and 3-edge-connected. This high level of connectivity makes the structure very robust.

Additionally, it is a 1-planar graph, meaning it can be drawn such that each edge is crossed at most once.

One of the most famous traits of this graph is that it is hypohamiltonian. In graph theory, a Hamiltonian cycle is a path that visits every vertex exactly once before returning to the start. The Coxeter graph does not contain such a cycle. However, if you remove any single vertex from the graph, the remaining structure becomes Hamiltonian.

This makes it a famous counterexample to certain versions of the Lovász conjecture. While it lacks a full cycle, it does contain a Hamiltonian path. It is one of only five known vertex-transitive graphs that lack Hamiltonian cycles.

There are several distinct ways to construct this mathematical object. The simplest method uses a Fano plane. First, you take the 35 possible 3-combinations of 7 objects. You then discard the 7 triplets that form the lines of the Fano plane. This leaves 28 triplets to serve as vertices. You connect two triplets if they are disjoint.

You can also build it from the Heawood graph. In this version, you create a vertex for every 6-cycle in the Heawood graph. You then connect vertices if their corresponding 6-cycles are disjoint.

Another construction method involves the Hoffman-Singleton graph. To do this, you select any vertex, which we can call vertex v, within the Hoffman-Singleton graph. You then identify an independent set of size 15 that includes vertex v. By deleting the 7 neighbors of vertex v along with the entire independent set, you are left with the Coxeter graph.

This shows how complex graphs can be nested within even larger mathematical structures.

The Coxeter graph is named after the mathematician Harold Scott MacDonald Coxeter. It is a highly symmetric object with an automorphism group of order 336. This group acts transitively on the vertices, edges, and arcs. Because of this, it is considered a symmetric graph. In the Foster census, it is identified as F28A. It holds the unique distinction of being the only cubic symmetric graph with exactly 28 vertices.

Algebraically, the graph is also uniquely identified by its spectrum. The spectrum is the set of eigenvalues from its adjacency matrix. The characteristic polynomial of the Coxeter graph is a specific mathematical expression. This polynomial is unique to this graph, meaning no other graph shares this exact spectrum. This allows mathematicians to recognize the Coxeter graph purely through its algebraic properties. It also has a rectilinear crossing number of 11. This makes it the smallest cubic graph to possess that specific crossing number.