Past exam of the mathematics course of the University of Cambridge / 2015 / ii / Paper 1 / 14I (Graph Theory)

A strongly regular graph with parameters $(k,a,b)$ is a simple graph in which each vertex has degree $k$, adjacent vertices have exactly $a$ common neighbours, and distinct nonadjacent vertices have exactly $b$ common neighbours. Its order $n$ is often included separately as a fourth parameter.

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.

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.