The McLaughlin graph is a 112-regular graph on 275 nodes and 
edges that can be constructed from the Witt design.
It is distance-regular with intersection
array 
.
It is also distance-transitive.
The first (isomorphic to the generalized quadrangle 
) and second subconstituents of
the McLaughlin graph are also distance-regular
(DistanceRegular.org).
To construct the graph, use the Witt design to create a 276-node graph 
that is not regular, but whose switching class is a regular two-graph. (Note that
a two-graph is not a graph, but is equivalent to a switching class of graphs. Any
one graph in the switching class determines the entire switching class.) The graph
has two types of vertex; the points
of the Witt design, and the blocks of the Witt design. Two vertices 
of 
are adjacent if and only if one of the following conditions
holds:
1. 
is a point and 
is a block not containing 
2. 
and 
are blocks that intersect in one point.
This yields a 276-vertex graph where each "point" vertex has degree 176 and each "block" vertex has degree 128.
It can also be constructed from the Leech lattice by starting with three lattice points that form the vertices of an isosceles
triangle with side lengths of 2, 2, and 
, identifying the exactly 275 lattice points that are
at distance 2 from each triangle vertex, and joining two points with an edge if they
are separated by distance 
. The resulting graph is the McLaughlin graph (Conway
and Sloane 1999, pp. 292-293; Gaucher 2013; Brouwer and van Maldeghem 2022,
p. 338).
A regular two-graph has the property that if we take a graph in the switching class, then we can "switch off" any vertex Consider the vertex 
corresponding to the point 0; then we can divide the remaining
vertices into three sets: 
is the 176 blocks that do not contain 0, 
is the 22 other points 
, and 
is the 77 blocks that do contain 0.
The partition 
is an equitable partition of the vertices of 
. More precisely, straightforward(ish) counting tells us that
1. Vertex 
is adjacent to 176 vertices in 
, 0 in 
, and 0 in 
.
2. Any vertex in 
is adjacent to vertex 
,
to 70 (other) vertices in 
, 15 vertices in 
and 42 vertices in 
.
3. Any vertex in 
is adjacent to 120 vertices in 
, 0 vertices in 
and 56 vertices in 
.
4. Any vertex in 
is adjacent to 96 vertices in 
, 16 in 
and 16 in 
.
If we now switch on the neighborhood of 
(which is the set 
) then every edge between a neighbor of 
and a non-neighbor of 
becomes a non-edge, and vice-versa. The effect of this is
that all the edges from 
to 
, 
to 
, 
to 
become non-edges and all non-edges from 
to 
, 
to 
, 
to 
become edges. In particular,
1. 
becomes an isolated vertex (all edges between 
and 
are turned from edges to non-edges)
2. every vertex in 
remains adjacent to 70 vertices in 
, but now becomes adjacent to 
vertices in 
and 
vertices in 
.
3. every vertex in 
becomes adjacent to 
vertices in 
,
remains adjacent to 0 in 
and remains adjacent to 56 in 
.
4. every vertex in 
becomes adjacent to 
vertices in 
and remains adjacent to 16 vertices in 
and 16 vertices in 
.
A quick calculation shows that the degree of each vertex in 
is 
, the degree of each vertex in 
is 
and the degree of each vertex in 
is 
. Thus if we throw away the vertex 
, then what remains is the 112-regular McLaughlin graph on
276 vertices.
The McLaughlin graph has independence number 22 (Brouwer), 4050 maximum independent
vertex sets (Brouwer), and 
maximal
independent vertex sets (R. Pratt, pers. comm., Dec. 11, 2011).
