Odd-4 Graph, Fano Planes, and the Coxeter Graph
Odd-4 Graph, Fano Planes, and the Coxeter Graph
The odd-4 graph is constructed by taking triplets from {1, 2, 3, 4, 5, 6, 7}, then connecting the triplets that share no values. Ignoring the colored edges, the entire 35-vertex graph is the odd-4 graph. The odd-3 graph is the Petersen graph, and the odd-2 graph is the pentagon.
A Fano plane is a collection of seven of these triplets where no two triplets share two numbers. The Fano plane is a structurally unique 7 point configuration, with 30 distinct numberings when the numbers 1-7 are assigned to the seven points. If a Fano plane is removed from the odd-4 graph, the result is the Coxeter graph, a non-Hamiltonian cubic symmetric graph with many interesting properties. If connections to the fifteen Fano planes of a single color are added instead, the result is the Hoffman–Singleton graph, which is also called the (7, 5)-cage.