Editing Higman–Sims graph (section)

==Construction==
===From M22 graph===
Take the [[M22 graph]], a [[strongly regular graph]] srg(77,16,0,4) and augment it with 22 new vertices corresponding to the points of S(3,6,22), each block being connected to its points, and one additional vertex ''C'' connected to the 22 points.

===From Hoffman–Singleton graph===
There are 100 [[independent set (graph theory)|independent set]]s of size 15 in the [[Hoffman–Singleton graph]]. Create a new graph with 100 corresponding vertices, and connect vertices whose corresponding independent sets have exactly 0 or 8 elements in common.
The resulting Higman–Sims graph can be partitioned into two copies of the [[Hoffman&ndash;Singleton graph]] in 352 ways.

===From a cube===
Take a cube with vertices labeled 000, 001, 010, ..., 111. Take all 70 possible 4-sets of vertices, and retain only the ones whose [[XOR]] evaluates to 000; there are 14 such 4-sets, corresponding to the 6 faces + 6 diagonal-rectangles + 2 parity tetrahedra. This is a 3-(8,4,1) [[block design]] on 8 points, with 14 blocks of block size 4, each point appearing in 7 blocks, each pair of points appearing 3 times, each triplet of points occurring exactly once. Permute the original 8 vertices any of 8! = 40320 ways, and discard duplicates. There are then 30 different ways to relabel the vertices (i.e., 30 different designs that are all isomorphic to each other by permutation of the points). This is because there are 1344 [[automorphism]]s, and 40320/1344 = 30.

Create a vertex for each of the 30 designs, and for each row of every design (there are 70 such rows in total, each row being a 4-set of 8 and appearing in 6 designs). Connect each design to its 14 rows. Connect disjoint designs to each other (each design is disjoint with 8 others). Connect rows to each other if they have exactly one element in common (there are 4x4 = 16 such neighbors). The resulting graph is the Higman–Sims graph. Rows are connected to 16 other rows and to 6 designs == degree 22. Designs are connected to 14 rows and 8 disjoint designs == degree 22. Thus all 100 vertices have degree 22 each.