Games graph

Several of the graph's properties follow immediately from this construction. It has ${\displaystyle 729=3^{6}}$ vertices, because the number of points in an affine space is the size of the base field to the power of the dimension. For each affine point, there are 56 lines through cap set points, 56 triangles containing the corresponding vertex, and ${\displaystyle 112=56\times 2}$ neighbors of the vertex. And there can be no triangles other than the ones coming from the construction, because any other triangle would have to come from three different lines meeting in a common plane of ${\displaystyle PG(6,3)}$, and the three cap set points of the three lines would all lie on the intersection of this plane with ${\displaystyle PG(5,3)}$, which is a line. But this would violate the defining property of a cap set that it has no three points on a line, so no such extra triangle can exist. The remaining property of strongly regular graphs, that all non-adjacent pairs of points have the same number of shared neighbors, depends on the specific properties of the 5-dimensional cap set.

With the ${\displaystyle 3\times 3}$ Rook's graph and the Brouwer–Haemers graph, the Games graph is one of only three possible strongly regular graphs whose parameters have the form ${\displaystyle {\bigl (}(n^{2}+3n-1)^{2},n^{2}(n+3),1,n(n+1){\bigr )}}$.^[4]

The same properties that produce a strongly regular graph from a cap set can also be used with an 11-point cap set in ${\displaystyle PG(4,3)}$, producing a smaller strongly regular graph with parameters (243,22,1,2).^[5] This graph is the Berlekamp–Van Lint–Seidel graph.^[6]