It was found by Hoffman & Singleton as example of a Moore graph
(a regular graph of girth 5 with the largest possible number
*k*^{2} + 1 of vertices). Two other Moore graphs are known,
namely the pentagon and the Petersen graph.
If there are other Moore graphs, they must have valency 57 and
3250 vertices.

The Hoffman-Singleton graph is the (7,5)-cage.

It is Hamiltonian.

The second construction uses the fact that it is possible to identify the 35 lines of PG(3,2) with the 35 triples from a 7-set in such a way that intersecting lines correspond to triples that have precisely one element in common. Now take as vertices the 15 points and 35 lines of PG(3,2), let the points form a coclique, let a point be adjacent to a line when they are incident, and let two lines be adjacent when the corresponding triples are disjoint.

The third construction produces the
Higman-Sims graph, together with
a split into two copies of Γ. In the
Steiner system S(4,7,23), fix an symbol *a*.
Construct the Higman-Sims graph on 1+22+77 points by taking a point *x*,
the 22 symbols distinct from *a* and the 77 blocks containing *a*,
where blocks are adjacent when they meet precisely in {*a*}.
Now let B be a block of S(4,7,23) not containing *a*.
We find a partition (1+7+42)+(15+35) of the 1+22+77 induced by B
(the 42 blocks are those meeting B in one point, the 35 those
meeting B in three points), and both 1+7+42 and 15+35 induce a
Hoffman-Singleton graph.

a) *A vertex*.
There are 50 of these, forming a single orbit.
The stabilizer of one (in the full automorphism group)
is S_{7} with vertex orbit sizes 1+7+42.
The subgraph induced on the second subconstituent is
the unique distance-regular graph with intersection array
{6,5,1;1,1,6}.

b) *A 15-coclique*.
There are 100 of these, forming a single orbit.
The stabilizer is A_{7} with vertex orbit sizes 15+35.
The complement of a 15-coclique is the unique distance-regular graph
with intersection array {4,3,3;1,1,2}, namely the
Odd graph O_{4}
of disjoint triples in a 7-set. It has full group S_{7},
with point stabilizer S_{3}×S_{4}.
The group is twice that of the Hoffman-Singleton graph since
this graph can be extended to a Hoffman-Singleton graph in two ways;
both occur in the Higman-Sims graph.

Two 15-cocliques meet in 0 (7x), 3 (35x), 5 (42x), 8 (15x) or 15 (1x) points. Meeting in 0, 5 or 15 is an equivalence relation, and the collection of 100 15-cocliques is the union of two collections of size 50. Being disjoint induces the structure of a Hoffman-Singleton graph on both.

The graph on the 15-cocliques, adjacent when they meet in 8 points,
is the unique distance-regular graph with intersection array
{15,14,10,3;1,5,12,15}. It has full group PSU(3,5).2 with
point stabilizer A_{7} and edge stabilizer L_{2}(7):2
(see below).

The graph on the 15-cocliques, adjacent when they meet in 0 or 8 is the Higman-Sims graph.

The two sets of 50 15-cocliques and the 50 vertices play a similar role (and there is an outer automorphism that interchanges the three). Thus, we can make a graph on 150 vertices, regular of valency 37, with a partition 50+50+50 such that the union of any two parts is the Higman-Sims graph.

c) *Split into two copies of 5C _{5}*.
There are 126 of these, forming a single orbit.
(The construction given above gives an explicit split.)
The stabilizer is 5

d) *An edge*.
There are 175 of these, forming a single orbit.
The stabilizer of one is A_{6}.2^{2}
with vertex orbit sizes 2+12+36.

The line graph of the Hoffman-Singleton graph is the unique
distance-regular graph with intersection array {12,6,5;1,1,4}.
Its distance-2 graph is strongly regular with parameters
*v* = 175, *k* = 72, λ = 20, μ = 36.
(It is the collinearity graph of a partial geometry pg(5,18,2)
constructed by Haemers. The collinearity graph of the dual pg(18,5,2)
has parameters *v* = 630, *k* = 85, λ = 20, μ = 10,
and full automorphism group Alt(7), transitive on the points.)

The subgraph induced on the orbit of size 36 is the Sylvester graph, the unique distance-regular graph with intersection array {5,4,2;1,1,4}.

e) *A pair of disjoint 15-cocliques*.
There are 350 of these, forming a single orbit.
The stabilizer of one is M_{10}
with vertex orbit sizes 20+30.

The subgraph induced on the orbit of size 20 is 10K_{2}.

The subgraph induced on the orbit of size 30 is Tutte's 8-cage, the incidence graph of the generalized quadrangle GQ(2,2).

f) *A Petersen graph*.
There are 525 of these, forming a single orbit.
The stabilizer of one is 2S_{5}.2
with vertex orbit sizes 10+40.

The subgraph induced on the orbit of size 40 is the unique (6,5)-cage.

Each hexagon of Γ is contained in a unique Petersen graph.

Each Petersen graph is split 5+5 in 6 splits into two 5C_{5}.
Each split into two 5C_{5} determines 25 Petersen graphs.
Each pair of splits determines a unique Petersen graph.
In this way we find the unital in PG(2,5^{2}), with
splits into two 5C_{5} as points, and Petersen graphs as lines.

g) *A Heawood graph*.
There are 750 of these, forming a single orbit.
The stabilizer of one is L_{2}(7):2
with vertex orbit sizes 8+14+28.
The 14 induces the Heawood graph.

Heawood subgraphs are equivalent to pairs of 15-cocliques meeting in 8 points: each half occurs in a unique 15-coclique and these two 15-cocliques meet in 8 points (and conversely, two 15-cocliques meeting in 8 points carry a Heawood graph on their symmetric difference).

The 28 induces the Coxeter graph.

A.E. Brouwer & J.H. van Lint,
*Strongly regular graphs and partial geometries*,
in: Enumeration and Design - Proc. Silver Jubilee Conf. on Combinatorics,
Waterloo, 1982,
D.M. Jackson & S.A. Vanstone (eds.)
Academic Press, Toronto (1984) 85-122.

W.H. Haemers,
*A new partial geometry constructed from the Hoffman-Singleton graph*,
Finite Geometries and designs, Proc. Second Isle of Thorns Conference 1980,
P.J. Cameron, J.W.P. Hirschfeld & D.R. Hughes (eds.),
London Math. Soc. Lecture Note Ser. **49**,
Cambridge University Press, Cambridge (1981) 119-127.

A.J. Hoffman & R.R. Singleton,
*On Moore graphs with diameters 2 and 3*,
IBM J. Res. Develop. **4** (1960) 497-504.

L.O. James,
*A combinatorial proof that the Moore (7,2) graph is unique*,
Utilitas Math. **5** (1974) 79-84.

G. Royle,
*Re: What is the Edge Chromatic Number of Hoffman-Singleton?*,
GRAPHNET@listserv.nodak.edu posting, 2004-09-29.

[BCN], Section 13.1.