Strongly regular graph

A strongly regular graph has constant degree and fixed common-neighbour counts for adjacent and nonadjacent vertex pairs.

For a finite simple graph with at least two vertices, no triangles, and exactly three common neighbours for every nonadjacent pair, the graph is connected. For adjacent vertices $u,v$, the bipartite graph between $N(u)\setminus \{v\}$ and $N(v)\setminus \{u\}$ has degree two at every vertex, forcing $d(u)=d(v)$. Thus the graph is regular. Counting second neighbours gives $3(n-d-1)=d(d-1)$. The nontrivial adjacency eigenvalues are $(-3\pm \sqrt{4d-3})/2$, and the larger-root multiplicity is $[n-1+d^2/\sqrt{4d-3}]/2$. Integrality forces $t=\sqrt{4d-3}$ to be an odd integer dividing $9$, yielding the stated degrees. The complete bipartite graph $K_{3,3}$ realizes degree three. The one-vertex graph is a vacuous exception with degree zero.

If a strongly regular graph on $n$ vertices has degree $d$, with $r$ common neighbours for adjacent vertices and $s$ for nonadjacent vertices, then its adjacency matrix satisfies

A connected regular graph is strongly regular exactly when its adjacency matrix has three distinct eigenvalues, apart from the complete graphs, which have two. The forward direction follows from the adjacency-matrix relation for a strongly regular graph; conversely, the quadratic polynomial vanishing on the two nonconstant eigenspaces is a scalar multiple of the all-ones matrix.