Past exam of the mathematics course of the University of Cambridge / 2019 / ii / Paper 1 / 17G / d

Suppose the only distinct eigenvalues are $d$ and $\theta$. As in part (c), $A$ acts by $d$ on $\mathrm{span}\{\mathbf{e}\}$ and by $\theta$ on ${\mathbf{e}}^{\perp }$, so its spectral decomposition isEvery diagonal entry of an adjacency matrix is zero, givingThus every off-diagonal entry is the same number $(d-\theta )/n=-\theta$. Since these entries belong to $\{0,1\}$ and the graph is connected with at least two vertices, that common value must be one. Hence $A=J-I$ and $G$ is the complete graph $K_n$.

Conversely, $K_n$ has adjacency matrix $J-I$, with eigenvalue $n-1$ on $\mathrm{span}\{\mathbf{e}\}$ and eigenvalue $-1$ on ${\mathbf{e}}^{\perp }$. Therefore the requested graphs are preciselyas stated by the connected regular graph with two adjacency eigenvalues characterization.