Paper 1, Section II, I

Graph Theory
Part II, 2015

(a) What does it mean to say that a graph GG is strongly regular with parameters (k,a,b)?(k, a, b) ?

(b) Let GG be an incomplete, strongly regular graph with parameters (k,a,b)(k, a, b) and of order nn. Suppose b1b \geqslant 1. Show that the numbers

12(n1±(n1)(ba)2k(ab)2+4(kb))\frac{1}{2}\left(n-1 \pm \frac{(n-1)(b-a)-2 k}{\sqrt{(a-b)^{2}+4(k-b)}}\right)

are integers.

(c) Suppose now that GG is an incomplete, strongly regular graph with parameters (k,0,3)(k, 0,3). Show that G{6,162}|G| \in\{6,162\}.