Hoffman–Singleton graph

4 October 2025

The #Mathober 2025 day 4 prompt is ‘Strongly’. I offer a diagram of the Hoffman–Singleton (HS) graph, which is a strongly regular graph:

A diagram of the Hoffman–Singleton graph, which has 50 vertices and 175 edges. The vertices are arranges in outer and inner circles of 25 each. The outer ones are grouped into 5 cycles drawn as pentagons; the inner ones into 5 cycles drawn as pentagrams. The remaining edges link the outer and inner vertices in a complicated but rotationally-symmetric way.

A graph is regular if each vertex has the same degree (number of neighbours) (in HS, 7). It is strongly regular if it is regular and, additionally, each pair of adjacent vertices have the same number of common neighbours (in HS, 0) and each pair of non-adjacent vertices have the same number of common neighbours (in HS, 1). HS is also a Moore graph. A Moore graph has the maximum number of vertices for a given diameter (maximum distance between vertices) and maximum degree.

In the diagram, the colours of the edges show how HS is made up of ten 5-cycles (5 drawn as pentagons on the outside; 5 as pentagrams on the inside), linked by other 125 other edges in a rotationally-symmetric way.

Same diagram in PDF format.