Past exam of the mathematics course of the University of Cambridge / 2026 / ii / Paper 3 / 17J (Graph Theory)

If $Av=\lambda v$, choose $i$ with $|v_i|$ maximal. Then $|\lambda ||v_i|=|{\sum }_{j\sim i}{v}_j|\le d(i)|v_i|\le \Delta |v_i|$, so $|\lambda |\le \Delta$.

For a $\Delta$-regular graph, $A1=\Delta 1$. Conversely equality in the preceding maximum-coordinate proof propagates equal absolute values and compatible signs through connectedness, forcing every vertex degree $\Delta$. Perron-Frobenius, or the same equality argument, makes the eigenspace one-dimensional.

$(A^r{)}_{ij}$ counts length-$r$ walks from $i$ to $j$, so $\mathrm{tr}{A}^r$ counts length-$r$ closed walks. The given power sums identify the spectrum as $5$ once, $\sqrt{5}$ and $-\sqrt{5}$ three times each, and $-1$ five times. Thus $n=12$, regular degree $d=5$, and the size is $nd/2=30$.

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.