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).