Past exam of the mathematics course of the University of Cambridge / 2015 / ii / Paper 1 / 14I / b / Solution

Let $A$ be the adjacency matrix of a graph, $J$ the all-ones matrix and $1$ the all-ones vector. Counting two-step walks givesBecause $b\ge 1$, any two nonadjacent vertices have a common neighbour, so the graph is connected. The eigenvalue $k$ is simple: for a real eigenvector at $k$, a maximal entry and the averaging equation force its neighbours, and then every vertex, to have the same value. Since $A$ is real symmetric, its other eigenvectors lie in $1^{\perp }$, where $J$ vanishes. Their eigenvalues are thereforeHere $d>0$ for the present incomplete connected graph. Indeed $k\ge b$; if $d=0$, then $k=b=a$, which conflicts with $a\le k-1$ for an edge. If $r,s$ have multiplicities $m_r,m_s$, dimension and zero trace give $m_r+m_s=n-1$ and $k+m_{r}r+m_{s}s=0$. ThusThese are dimensions of eigenspaces, hence integers. A multiplicity may be zero; that does not affect the conclusion.