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.
Although its parameters are those of the point graph of a partial geometry 
, Östergård and Soicher (2016) proved that
the corresponding McLaughlin geometry does
not exist.
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 iff
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 vertex degree 176 and each "block" vertex has vertex 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 1, 2, ...,
22, and 
is the 77 blocks that do contain 0.
The set partition 
is an equitable set partition
of the vertices of 
. More precisely, straightforward(ish) counting tells us that
1. Graph 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 open graph 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 vertex degree of each vertex in 
is 
, the vertex degree
of each vertex in 
is 
and the vertex degree
of each vertex in 
is 
. Thus if we throw away the vertex 
, then what remains is the 112-regular
graph called the McLaughlin graph on 275 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).
