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

Count edges from the $k$ neighbours of a fixed vertex to its $n-k-1$ nonneighbours. Each neighbour contributes $k-a-1$ such edges, and each nonneighbour receives $b$. With $a=0,b=3$,The graph is incomplete, so there are nonadjacent vertices and $k\ge 3$. Substituting into the eigenvalue multiplicity formula gives a multiplicity difference of $k^2/\sqrt{4k-3}$. This must be an integer. As $k>0$, $d=\sqrt{4k-3}$ is rational and hence an integer; it is positive and odd. Moreover $d\mid k^2$ and $4k=d^2+3$, so reducing $16k^2$ modulo $d$ gives $d\mid 9$. Thus $d\in \{1,3,9\}$. The value $d=1$ gives $k=1$, impossible here; the other two give $(k,n)=(3,6)$ and $(21,162)$. Consequently $|G|\in \{6,162\}$. This is a necessity argument, not a claim that integrality alone constructs either graph.