4.II.17F

Graph Theory
Part II, 2006

What is meant by a graph GG of order nn being strongly regular with parameters (d,a,b)?(d, a, b) ? Show that, if such a graph GG exists and b>0b>0, then

12{n1+(n1)(ba)2d(ab)2+4(db)}\frac{1}{2}\left\{n-1+\frac{(n-1)(b-a)-2 d}{\sqrt{(a-b)^{2}+4(d-b)}}\right\}

is an integer.

Let GG be a graph containing no triangles, in which every pair of non-adjacent vertices has exactly three common neighbours. Show that GG must be dd-regular and G=1+d(d+2)/3|G|=1+d(d+2) / 3 for some d{1,3,21}d \in\{1,3,21\}. Show that such a graph exists for d=3d=3.