Past exam of the mathematics course of the University of Cambridge / 2026 / ii / Paper 3 / 17J / c / Solution

Strong regularity $(n,d,a,b)$ means degree $d$, with $a$ common neighbours for adjacent pairs and $b$ for nonadjacent pairs. Counting two-step walks gives $(n-d-1)b=d(d-a-1)$; eigenvalue multiplicities impose the standard rationality condition. Here $a=0,b=3$, so $n=1+d(d+2)/3$. Applying multiplicity integrality to roots of $x^2+3x+3-d$ leaves $d\in \{1,3,21\}$. For $d=3$, $K_{3,3}$ is the required example.