Hoffman–Singleton graph

Hoffman–Singleton graph
Named after	Alan J. Hoffman Robert R. Singleton
Vertices	50
Edges	175
Radius	2
Diameter	2
Girth	5
Automorphisms	252,000 (PSU(3,52):2)
Chromatic number	4
Chromatic index	7
Genus	29
Properties	Strongly regular Symmetric Hamiltonian Integral Cage Moore graph

In the mathematical field of graph theory, the Hoffman–Singleton graph is a 7-regular undirected graph with 50 vertices and 175 edges. It is the unique strongly regular graph with parameters (50,7,0,1). It was constructed by Alan Hoffman and Robert Singleton while trying to classify all Moore graphs, and is the highest order Moore graph known to exist. Since it is a Moore graph where each vertex has degree 7, and the girth is 5, it is a (7,5)-cage.

Here are two constructions of the Hoffman–Singleton graph.

Take five pentagons P_h and five pentagrams Q_i . Now join vertex j of P_h to vertex h·i+j of Q_i. (All indices are modulo 5.)

Any set of seven points (as abstract mathematical objects) can be made into a Fano plane by adding seven lines to them. By permuting the points, a set of 30 different Fano planes can be generated, where two Fano planes are considered identical if they differ solely in the order of points within a line or the order of lines in the plane . Among these 30 different Fano planes on the same points, each subset of three points is used as a line in 6 out of 30 of the planes. For any one of these 30 Fano planes, there are 14 others that share exactly one line with it. The same set of seven points also has 35 different three-element subsets ("triads"), counted by the binomial coefficient ${\displaystyle {\tbinom {7}{3}}=35}$. The Hoffman–Singleton graph can then be built from two sets of vertices:

...
Wikipedia