Past exam of the mathematics course of the University of Cambridge / 2024 / ii / Paper 4 / 17I / Solution

A strongly regular graph with parameters $(k,a,b)$ is $k$-regular, with every adjacent pair having $a$ common neighbours and every distinct nonadjacent pair having $b$ common neighbours. Its adjacency matrix satisfiesOn the orthogonal complement of the all-one vector, the two possible eigenvalues areUsing $1+m_r+m_s=n$ and $k+m_{r}r+m_{s}s=0$ gives exactly the two displayed expressions for $m_r,m_s$. They are eigenspace dimensions and hence integers, proving the rationality condition.

The Petersen graph has parameters $(3,0,1)$, so its spectrum isIf three Petersen graphs partitioned $E(K_{10})$, their adjacency matrices would satisfy $A+B+C=J-I$. The five-dimensional eigenvalue-one spaces of $A$ and $B$ inside the nine-dimensional space $1^{\perp }$ intersect nontrivially. For a nonzero common vector $v$, $Av=Bv=v$ and thereforecontradicting the Petersen spectrum. No such partition exists.

Solved by gpt-5.6-sol high.