Past exam of the mathematics course of the University of Cambridge / 2019 / ii / Paper 1 / 17G (Graph Theory)

Let $A$ be the adjacency matrix of a graph. Since $G$ is a regular graph of degree $d$, every row of $A$ sums to $d$. Therefore, for $\mathbf{e}=(1,\dots ,1{)}^T$,so $d$ is a graph eigenvalue.

If $Av=dv$, then the quadratic form of the Graph Laplacian $L=dI-A$ givesEvery summand is nonnegative, so $v_i=v_j$ along every edge. The graph is connected, hence all coordinates of $v$ are equal and $v$ is a scalar multiple of $\mathbf{e}$. Thus the $d$-eigenspace is one-dimensional. Since $A$ is a symmetric matrix, the spectral theorem for real symmetric matrices makes it diagonalizable, so the algebraic multiplicity is also one. This proves the constant eigenvector of a regular graph result.

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 iswhere $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 givesThere are at most two possible roots $\theta$ in addition to $d$. Thus $G$ has at most three distinct eigenvalues.

For an eigenvector $v$ with eigenvalue $\theta \in \{\lambda ,\mu \}$,By part (a), every vector orthogonal to $\mathbf{e}$ is a linear combination of such eigenvectors, so $B$ vanishes on ${\mathbf{e}}^{\perp }$. On the remaining eigenspace,The orthogonal projection onto $\mathrm{span}\{\mathbf{e}\}$ is $J/n$. It follows thatPut $\kappa =(d-\lambda )(d-\mu )/n$. For $i\ne j$, the identity $B=\kappa J$ readsand thereforeBecause $(A^2{)}_{ij}$ is the number of common neighbours, these two constants prove that $G$ is strongly regular. This is the converse half of the three-eigenvalue characterization of a connected strongly regular graph.

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.