= Solution
Suppose the <strongly regular graph> has $n$ vertices, degree $d$, $r$ common neighbours for every adjacent pair and $s$ common neighbours for every nonadjacent pair. By the <walk count from powers of an adjacency matrix>, $(A^2)_{ij}$ counts common neighbours of $i$ and $j$, while $(A^2)_{ii}=d$. Hence the <adjacency-matrix relation for a strongly regular graph> is
$$
A^2=(d-s)I+(r-s)A+sJ,
$$
where $J$ is the <all-ones matrix>.
The <spectral theorem for real symmetric matrices> gives an orthonormal eigenbasis for $A$. Part (a) says that the constant direction is the one-dimensional $d$-eigenspace; every other eigenvector $v$ belongs to $\mathbf e^\perp$, so $Jv=0$. If $Av=\theta v$, the displayed identity gives
$$
\theta^2-(r-s)\theta-(d-s)=0.
$$
There are at most two possible roots $\theta$ in addition to $d$. Thus $G$ has at most three distinct eigenvalues.
Back to article page
