It can also be described as the graph on the 77–21 = 56 blocks of the (unique) Steiner system S(3,6,22) not containing a fixed symbol, adjacent when they are disjoint. Or, equivalently, as the graph on the 56 hyperovals from one L3(4) orbit in PG(2,4), adjacent when they are disjoint. Or again, equivalently, as the graph on the 56 octads that contain two given symbols a,b but not a third symbol c, where two octads are adjacent when they meet in just {a,b}.
b) An edge. There are 280 of these, forming a single orbit. The stabilizer of one is 32:Q8.2×2 with vertex orbit sizes 2+18+36. In PG(2,4) these can be identified with the unitals (AG(2,3) subplanes): the complement of the union of two disjoint hyperovals is a unital. The graph on the 280 edges, where two edges are adjacent when they are opposite edges of a quadrangle, is distance-transitive with intersection array {9,8,6,3;1,1,3,8} and spectrum 91 464 1105 (–3)90 (–5)20. Its automorphism group Aut (L3(4)) is three times larger than that of the Gewirtz graph. The uniqueness of this graph (given its parameters) was shown by Lambeck.
c) A 16-coclique. There are 42 of these, forming a single orbit. The stabilizer of one is 24.S5 with vertex orbit sizes 16+40. In the Higman-Sims graph these are visible as point neighbourhoods. Also in PG(2,4) these 16-cocliques are visible: each point is in 16 of our hyperovals, and these hyperovals are mutually nonadjacent. Moreover, each hyperoval has six exterior lines forming a dual hyperoval, and disjoint hyperovals have disjoint dual hyperovals; it follows that the 21 lines of PG(2,4) also give 16-cocliques. The graph on the 16-cocliques, adjacent when disjoint, is the point-line incidence graph of PG(2,4). Distance 0,1,2,3 in this graph corresponds to an intersection of size 16,0,4,6, respectively.
d) 6 C4. There are 105 of these, forming a single orbit. The stabilizer of one is 22+4.3.22 with vertex orbit sizes 24+32. Each quadrangle determines a unique subgraph 6 C4, and hence there are 105 such subgraphs. The complement of one is the bipartite point-block incidence graph of AG(2,4) from which a parallel class of lines has been removed. In particular, we find partitions of the Gewirtz graph into one subgraph 6 C4 and two 16-cocliques. This pair of 16-cocliques can be viewed as a flag in PG(2,4). There are no other regular subgraphs of valency 2 on 24 vertices.
e) 10 K2 and Sylvester. There are 112 of these, forming a single orbit. The stabilizer of one is M10 with vertex orbit sizes 20+36.
A hyperoval of a non-chosen orbit meets our hyperovals in 1 or 3 points; 20 in 3 (each triple occurs once) and 36 in 1. This induces a partition of the graph into two subgraphs, one isomorphic to 10 K2, the other to the Sylvester graph (distance-regular with intersection array {5,4,2;1,1,4} on 36 vertices).
A different way to see this is to look at the Higman-Sims graph. It has splits into two Hoffman-Singleton graphs. Choosing an edge in one of the Hoffman-Singleton graphs we find that the subgraph of the Higman-Sims graph far away from that edge is split into a Sylvester graph and a 10 K2.
A different way to see the presence of subgraphs 10 K2 is by looking at the generalized quadrangle GQ(3,9) on 112 vertices. It has splits into two Gewirtz graphs, and the ten lines on a point on one side meet the other side in 10 K2.
f) co-Heawood graph. (The co-Heawood graph is the point-line nonincidence graph of the Fano plane.) There are 120 of these, forming a single orbit. The stabilizer of one is L2(7):2×2 with vertex orbit sizes 7+7+42. Their presence can be seen from the M24 construction: if our Gewirtz graph consists of the octads starting 110, then fix an octad B starting 001. There are 7, 42, 7 octads in our graph that meet B in 4, 2, 0 vertices, respectively, and the 7+7 induces a co-Heawood graph. The involution in M24 that fixes B pointwise, and fixes the pair contained in all Gewirtz octads fixes the co-Heawood graph pointwise. There is no automorphism here interchanging the two 7-cocliques in the co-Heawood graph.
g) Splits into two Coxeter graphs. The Gewirtz graph has 240 splits into two Coxeter graphs, forming a single orbit. The stabilizer of one split is L2(7):2 with vertex orbit sizes 28+28.
These splits can be seen inside the Higman-Sims graph. It has splits into two Hoffman-Singleton graphs. Choosing an edge that meets both sides we find that the subgraph of the Higman-Sims graph far away from that edge is split into two Coxeter graphs.
A different way to see these is to look at the M24 construction: if our Gewirtz graph consists of the octads starting 110, then fix an octad B starting 100 or 010. There are 28, 28 octads in our graph that meet B in 3, 1 vertices, respectively, and thus each B gives a split.
h) Extended bipartite double of the Petersen graph. There are 336 of these, forming a single orbit. The stabilizer of one is S5×2 with vertex orbit sizes 6+20+30. The extended bipartite double of the Petersen graph has 20 vertices and spectrum 41 25 14 (–1)4 (–2)5 (–4)1. Inside the Higman-Sims graph it can be seen by taking a path a ~ b ~ c ~ d of length 3, and taking the 20 vertices adjacent to one of a, d and none of b, c.
size # 7 240 9 2520 10 43960 11 20160 12 5460 13 1680 16 42A colouring with 4 colours must use two disjoint 16-cocliques. The complement of their union is the union of six quadrangles, in particular bipartite. Any 2-colouring of this 6 C4 either determines two maximal 12-cocliques, or a maximal 12-coclique and a 16-coclique. See also d) above.
A. Gewirtz, Graphs with maximal even girth, Canad. J. Math. 21 (1969) 915-934.
A. Gewirtz, The uniqueness of g(2,2,10,56), Trans. New York Acad. Sci. 31 (1969) 656-675.
M. Hall, jr., R. Lane & D. Wales, Designs derived from permutation groups, J. Combin. Th. 8 (1970) 12-22.
A.E. Brouwer & W.H. Haemers, The Gewirtz graph - an exercise in the theory of graph spectra, Europ. J. Comb. 14 (1993) 397-407.
E.W. Lambeck, The uniqueness of a distance-regular graph on 280 vertices, in: Contributions to the theory of distance regular graphs, Ph.D. Thesis, Techn. Univ. Eindhoven, Netherlands, 1990.