40.06.09 · combinatorics / design-coding-theory

Strongly Regular Graphs and the Design-Graph Dictionary

shipped3 tiersLean: none

Anchor (Master): van Lint-Wilson 2001 *A Course in Combinatorics* 2e Ch. 21 and Ch. 30 (strongly regular graphs, the absolute bound, association schemes); Brouwer-Cohen-Neumaier 1989 *Distance-Regular Graphs* (Springer) Ch. 1-3 (SRGs as the diameter-2 case, the Krein conditions, the absolute bound); Brouwer-Haemers 2012 *Spectra of Graphs* (Springer) Ch. 9; Hoffman-Singleton 1960 *IBM J. Res. Develop.* 4 (Moore graphs of diameter 2); Seidel 1968 (regular two-graphs and equiangular lines)

Intuition Beginner

Imagine a social club where everyone has exactly the same number of friends, and where the friendship pattern is unusually orderly. Pick any two members who are friends: they always share the same number of mutual friends, say two. Pick any two who are strangers: they too share a fixed number of mutual friends, say one. A network this regular — one rule for friends, one for strangers, the same number of friends for everyone — is a strongly regular graph. The dots are members, a line means friendship, and strong regularity promises that the local picture around any pair looks like the picture around any other pair of the same kind.

Four numbers describe such a club. There are $v$ members in total; everyone has exactly $k$ friends; every pair of friends shares $λ$ mutual friends; every pair of strangers shares $μ$ mutual friends. Once you fix these four counts, the network is squeezed into a very rigid shape. You cannot pick the four numbers freely — they must fit together, and only special combinations describe a real club. This is the same kind of rigidity you met with block designs, where a few parameters force everything else.

The headline fact of this unit is that this rigidity becomes arithmetic. From the four counts you can compute hidden whole numbers — how many times certain patterns repeat — and those hidden numbers must come out as honest non-negative integers. When they do not, no such network exists, and you have ruled out a whole family of clubs with one short calculation.

Visual Beginner

The picture-perfect example is the Petersen graph: ten dots, each joined to three others, drawn as an outer five-pointed ring and an inner five-pointed star, with spokes joining the two.

In the Petersen graph every dot has exactly $3$ friends, so $k = 3$ . Pick any two dots that are joined: they have no friend in common, so $λ = 0$ . Pick any two dots that are not joined: they have exactly one friend in common, so $μ = 1$ . With $v = 10$ dots, the four counts are $(v, k, λ, μ) = (10, 3, 0, 1)$ .

quantity	symbol	value in Petersen
vertices	$v$	$10$
degree (friends each)	$k$	$3$
common friends of an adjacent pair	$λ$	$0$
common friends of a non-adjacent pair	$μ$	$1$

Read the table against the drawing. Because $λ = 0$ , no two joined dots sit in a triangle, so the graph has no triangles. Because $μ = 1$ , any two unjoined dots are linked by exactly one length-two path. These two rules, holding everywhere at once, are what "strongly regular" means.

Worked example Beginner

Let us recover a hidden count for the Petersen graph using only the four numbers, and check it comes out whole. Take $(v, k, λ, μ) = (10, 3, 0, 1)$ . We will find how many dots are strangers to a fixed dot, and verify a balance rule the four numbers must obey.

Step 1. Fix one dot $P$ . It has $k = 3$ friends. The remaining dots, other than $P$ and its friends, are the strangers to $P$ : that is $v - 1 - k = 10 - 1 - 3 = 6$ strangers.

Step 2. Count, two ways, the lines that run from $P$ 's friends to $P$ 's strangers. Each of the $3$ friends of $P$ has $k = 3$ lines. One of those goes back to $P$ . The friends of $P$ share $λ = 0$ mutual friends with $P$ , so no line runs between two friends of $P$ . So each friend sends all its other $k - 1 - λ = 3 - 1 - 0 = 2$ lines out to strangers. That is $3 \times 2 = 6$ lines reaching strangers.

Step 3. Now count the same lines from the strangers' side. Each stranger shares $μ = 1$ mutual friend with $P$ , so each stranger is joined to exactly $1$ of $P$ 's friends. With $6$ strangers, that is $6 \times 1 = 6$ lines. The two counts agree: $6 = 6$ .

What this tells us: the four numbers are not independent. Counting the friend-to-stranger lines two ways forces the balance $k (k - 1 - λ) = (v - 1 - k) μ$ . Here $3 \cdot 2 = 6 \cdot 1$ . Whenever this rule fails, no strongly regular graph with those four counts can exist.

Check your understanding Beginner

Formal definition Intermediate+

Throughout, $A$ denotes the adjacency matrix of a graph $G$ on vertex set ${1, \dots, v}$ (so $A_{ij} = 1$ if $i \sim j$ and $0$ otherwise, with zero diagonal), $I$ the identity, $J$ the all-ones matrix, and $1$ the all-ones column vector, of the size context demands. The arguments use the real spectral theorem for symmetric matrices and the rank and trace theory of finite-dimensional vector spaces (01.01.05) as background; the incidence-matrix viewpoint and the identity $N N^{⊤} = (r - λ) I + λ J$ for $2$ -designs are carried over from 40.06.01, where the same passage from a combinatorial axiom to a matrix equation was made.

Definition (strongly regular graph). A graph $G$ on $v$ vertices is strongly regular with parameters $(v, k, λ, μ)$ , written $srg (v, k, λ, μ)$ , if it is $k$ -regular ( $0 < k < v - 1$ ), every pair of adjacent vertices has exactly $λ$ common neighbours, and every pair of distinct non-adjacent vertices has exactly $μ$ common neighbours. The cases $k = 0$ , $k = v - 1$ , and disconnected or complete graphs are excluded as degenerate. The complement $\overline{G}$ is again strongly regular, with parameters $(v, v - k - 1, v - 2 k + μ - 2, v - 2 k + λ)$ .

Proposition (the adjacency equation). $G$ is $srg (v, k, λ, μ)$ if and only if its adjacency matrix satisfies $$ A^2 = kI + \lambda A + \mu (J - I - A), $$ together with $A J = k J$ (the regularity). The $(i, i)$ entry of $A^{2}$ is the number of closed length- $2$ walks at $i$ , namely $k$ ; for $i \neq = j$ adjacent the $(i, j)$ entry is the number of common neighbours, $λ$ ; for $i \neq = j$ non-adjacent it is $μ$ . The matrix $J - I - A$ is the adjacency matrix of the complement, with a $1$ exactly at non-adjacent distinct pairs, so the right-hand side reproduces $A^{2}$ entry by entry. Rearranged, $A^{2} - (λ - μ) A - (k - μ) I = μ J$ .

Proposition (parameter feasibility). Counting common neighbours of a fixed vertex across the edge between its neighbour-set and non-neighbour-set gives the identity $$ k(k - \lambda - 1) = (v - k - 1)\mu . $$ This is the necessary arithmetic relation among the four parameters; it expresses that the $k (k - λ - 1)$ edges leaving the neighbourhood of a vertex are exactly the $μ$ links each of the $v - k - 1$ non-neighbours sends back.

Definition (eigenvalues and multiplicities). Since $A$ is symmetric it is diagonalisable with real eigenvalues. The all-ones vector $1$ is an eigenvector with eigenvalue $k$ . On the orthogonal complement $1^{⊥}$ , the term $μ J$ vanishes, so $A^{2} - (λ - μ) A - (k - μ) I = 0$ there: every other eigenvalue is a root of $$ x^2 - (\lambda - \mu) x - (k - \mu) = 0 , $$ with roots $$ r, s = \tfrac12\Big( (\lambda - \mu) \pm \sqrt{(\lambda - \mu)^2 + 4(k - \mu)} \Big), \qquad r > s . $$ Their multiplicities $f$ (for $r$ ) and $g$ (for $s$ ) satisfy $f + g = v - 1$ and, from $tr A = 0 = k + f r + g s$ , $$ f, g = \frac{1}{2}\left( (v-1) \mp \frac{2k + (v-1)(\lambda - \mu)}{r - s} \right). $$ A conference graph is a strongly regular graph in the half case $f = g$ ; otherwise $r, s$ are integers (the integer case).

Counterexamples to common slips Intermediate+

Strong regularity is a condition on common neighbours of pairs, not on the degree alone. A $k$ -regular graph need not be strongly regular; the cycle $C_{6}$ is $2$ -regular but adjacent pairs have $0$ common neighbours while some non-adjacent pairs have $1$ and others $0$ , so $μ$ is not constant.
The disconnected and complete cases are degenerate, not genuine SRGs. A disjoint union of cliques $m K_{n}$ formally satisfies the equation with $μ = 0$ ; excluding $μ = 0$ (equivalently requiring $G$ and $\overline{G}$ connected) keeps the eigenvalue theory non-degenerate. The standard convention restricts to $0 < μ$ , $0 < k < v - 1$ .
The eigenvalue $r$ need not be an integer. In the half case ( $f = g$ ) the restricted eigenvalues are $r, s = \frac{1}{2} (- 1 \pm v)$ , irrational; the Paley graph on $13$ vertices is an example. Integrality of the eigenvalues is forced only when $f \neq = g$ .
$λ$ and $μ$ are not interchangeable. Swapping them does not give the complement; the complement's parameters are $(v, v - k - 1, v - 2 k + μ - 2, v - 2 k + λ)$ , a specific shift, not a transposition of $λ$ and $μ$ .

Key theorem with proof Intermediate+

The single equation $A^{2} = k I + λ A + μ (J - I - A)$ converts strong regularity into a three-dimensional matrix algebra and forces the eigenvalue multiplicities to be integers. That integrality is the rationality condition, and it is the most powerful elementary non-existence tool for SRGs.

Theorem (eigenvalues, multiplicities, and the rationality condition). Let $G$ be $srg (v, k, λ, μ)$ with adjacency matrix $A$ . Then $A$ has eigenvalue $k$ with multiplicity $1$ , and exactly two further eigenvalues $$ r, s = \tfrac12\Big( (\lambda - \mu) \pm \sqrt{(\lambda-\mu)^2 + 4(k-\mu)},\Big), \quad r > s, $$ with multiplicities $$ f, g = \frac{1}{2}\left( (v-1) \mp \frac{2k + (v-1)(\lambda-\mu)}{r-s}\right), \qquad f + g = v - 1 . $$ Since $f, g$ are non-negative integers, either (integer case) $D := (λ - μ)^{2} + 4 (k - μ)$ is a perfect square and $r, s \in Z$ , or (half case) $2 k + (v - 1) (λ - μ) = 0$ , forcing $f = g$ and parameters $(v, k, λ, μ) = (4 t + 1, 2 t, t - 1, t)$ ^{[van Lint-Wilson Ch. 21]}.

Proof. The graph is $k$ -regular, so $A 1 = k 1$ : $k$ is an eigenvalue with eigenvector $1$ . By the feasibility identity $k$ is simple (the complement is connected, so $J$ and $A$ share only the eigenvector $1$ at eigenvalue $k$ ). The rearranged equation reads $A^{2} - (λ - μ) A - (k - μ) I = μ J$ . Apply both sides to a vector $x \in 1^{⊥}$ : then $J x = 0$ , so $(A^{2} - (λ - μ) A - (k - μ) I) x = 0$ . Any eigenvalue $θ \neq = k$ of $A$ has its eigenvector in $1^{⊥}$ (orthogonality of eigenvectors of the symmetric matrix $A$ ), so $θ^{2} - (λ - μ) θ - (k - μ) = 0$ . The two roots are $r, s$ as stated, and $r - s = (λ - μ)^{2} + 4 (k - μ) = D > 0$ .

Let $f, g$ be the multiplicities of $r, s$ . Counting dimensions, $1 + f + g = v$ , so $f + g = v - 1$ . Taking the trace, $tr A = 0$ because the diagonal of $A$ is zero; hence $k + f r + g s = 0$ . Substituting $g = v - 1 - f$ and solving the linear system ${f + g = v - 1, f r + g s = - k}$ gives $$ f = \frac{1}{2}\left((v-1) - \frac{2k + (v-1)(\lambda-\mu)}{r - s}\right), \qquad g = \frac{1}{2}\left((v-1) + \frac{2k + (v-1)(\lambda-\mu)}{r-s}\right), $$ using $r + s = λ - μ$ . Now $f, g \in Z_{\geq 0}$ . If the fraction $\frac{2 k + ( v - 1 ) ( λ - μ )}{r - s}$ is irrational, the only way $f, g$ can be rational is for its numerator to vanish: $2 k + (v - 1) (λ - μ) = 0$ , giving $f = g = (v - 1) /2$ . This is the half case; with $r + s = λ - μ$ and the feasibility relation it forces $μ = k /2$ , $λ = μ - 1$ , and $v = 2 k + 1$ , i.e. $(4 t + 1, 2 t, t - 1, t)$ with $k = 2 t$ . Otherwise the fraction is rational, which (as $r - s = D$ ) forces $D \in Q$ , hence $D$ a perfect square and $r, s \in Z$ . $□$

Bridge. This theorem builds toward the whole spectral theory of association schemes and appears again in the Krein conditions and absolute bound below, because it shows that a strongly regular graph is governed by a three-dimensional commutative algebra $⟨ I, A, J ⟩$ whose idempotents have integer ranks. The foundational reason an SRG is rigid is exactly this: the matrix carries only three eigenvalues, so its adjacency algebra is the smallest non-degenerate Bose-Mesner algebra, and that is the central insight tying SRGs to the rank- $v$ rigidity of $2$ -designs in 40.06.01. This is dual to the design picture, where the concurrence matrix $N N^{⊤} = (r - λ) I + λ J$ had the same two-eigenvalue shape; putting these together, an SRG is the graph a symmetric design draws on its blocks, and the integrality of design parameters generalises to the integrality of SRG multiplicities. The bridge is that strong regularity, a local common-neighbour count, is encoded losslessly in the spectrum of one symmetric ${0, 1}$ matrix.

Exercises Intermediate+

Exercise 5 (medium, symbolic).

Prove the feasibility identity $k (k - λ - 1) = (v - k - 1) μ$ by counting, for a fixed vertex $x$ , the edges between $N (x)$ (its neighbours) and $V ∖ ({x} \cup N (x))$ (its non-neighbours).

Hint

Each neighbour of $x$ has $k$ edges; subtract the edge to $x$ and the $λ$ edges to other neighbours. Each non-neighbour sends $μ$ edges into $N (x)$ .

Answer

Fix $x$ . A neighbour $y \in N (x)$ has degree $k$ ; one edge goes to $x$ , and $λ$ edges go to common neighbours of $x$ and $y$ (which lie in $N (x)$ ), so $y$ sends $k - 1 - λ$ edges to non-neighbours of $x$ . Summing over the $k$ neighbours gives $k (k - 1 - λ)$ such edges. Counting from the other side, a non-neighbour $z$ shares $μ$ common neighbours with $x$ , i.e. sends $μ$ edges into $N (x)$ ; with $v - k - 1$ non-neighbours this is $(v - k - 1) μ$ edges. The two counts of the same edge set agree: $k (k - λ - 1) = (v - k - 1) μ$ . Rubric: full credit for both counts and the identification of the edge set.

Exercise 7 (hard, symbolic).

Prove the friendship theorem: if a finite graph has the property that every two distinct vertices have exactly one common neighbour, then some vertex is adjacent to all others (a "politician"). Reduce to the regular case and apply the SRG eigenvalue machinery.

Hint

If no politician exists, show the graph is regular of some degree $k$ , hence $srg (v, k, 1, 1)$ ; then force a contradiction from the integrality of the eigenvalue multiplicities.

Answer

Assume the "exactly one common neighbour" condition and that no vertex is adjacent to all others. First, non-adjacent vertices have equal degree: if $u \neq \sim w$ , their unique common neighbour and a counting of paths gives $d (u) = d (w)$ ; the no-politician hypothesis makes the non-adjacency graph connected, so all degrees are equal to some $k$ . Thus $G$ is $srg (v, k, 1, 1)$ with $v = k^{2} - k + 1$ (from feasibility $k (k - 2) = (v - k - 1) \cdot 1$ ). The restricted eigenvalues solve $x^{2} - 0 \cdot x - (k - 1) = 0$ , so $r, s = \pm k - 1$ . The multiplicities are $f, g = \frac{1}{2} ((v - 1) \mp \frac{2 k}{2 k - 1}) = \frac{1}{2} ((v - 1) \mp \frac{k}{k - 1})$ . For these to be integers with $r \neq = s$ , $k - 1$ must divide $k$ ; but $g cd (k - 1, k) = 1$ forces $k - 1 = 1$ , i.e. $k = 2$ , giving the triangle $v = 3$ — which does have a politician. The contradiction shows a politician must exist. Rubric: full credit for the reduction to regularity, the $srg (v, k, 1, 1)$ identification, the eigenvalues $\pm k - 1$ , and the divisibility contradiction.

Exercise 8 (hard, symbolic).

Prove the Hoffman-Singleton restriction: a Moore graph of diameter $2$ and girth $5$ — equivalently an $srg (k^{2} + 1, k, 0, 1)$ — exists only for $k \in {2, 3, 7, 57}$ . Use the integrality of the eigenvalue multiplicities.

Hint

The eigenvalues are $\frac{1}{2} (- 1 \pm 4 k - 3)$ . Write the multiplicity-difference condition and require it to be an integer; analyse when $4 k - 3$ is irrational versus rational.

Answer

A Moore graph of diameter $2$ , girth $5$ is $srg (k^{2} + 1, k, 0, 1)$ : $v = k^{2} + 1$ since each of the $k$ neighbours of a vertex contributes $k - 1$ new vertices with no collisions ( $μ = 1$ , $λ = 0$ ). The restricted eigenvalues solve $x^{2} + x - (k - 1) = 0$ , so $r, s = \frac{1}{2} (- 1 \pm 4 k - 3)$ , and $r - s = 4 k - 3$ . The multiplicities are $f, g = \frac{1}{2} (k^{2} \mp \frac{2 k - k ^{2}}{4 k - 3})$ . If $4 k - 3$ is irrational, integrality forces $2 k - k^{2} = 0$ , i.e. $k = 2$ (the pentagon). Otherwise $4 k - 3 = u^{2}$ for an integer $u$ ; then $u ∣ k^{2} - 2 k$ , and since $16 (k^{2} - 2 k) = (u^{2} + 3)^{2} - 10 (u^{2} + 3) + \dots$ reduces to $u ∣ 15$ , giving $u \in {1, 3, 5, 15}$ and $k = \frac{u ^{2} + 3}{4} \in {1, 3, 7, 57}$ . Discarding $k = 1$ , the feasible degrees are $k \in {2, 3, 7, 57}$ , realised by the pentagon, the Petersen graph, and the Hoffman-Singleton graph; $k = 57$ is open. Rubric: full credit for the parameter identification, the eigenvalues, the irrational-case $k = 2$ , and the divisibility $u ∣ 15$ giving ${3, 7, 57}$ .

Advanced results Master

The adjacency equation makes the span $⟨ I, A, J ⟩$ a $3$ -dimensional commutative algebra closed under matrix multiplication and entrywise (Schur) multiplication: the Bose-Mesner algebra of a two-class association scheme. The deeper feasibility conditions — the absolute bound and the Krein conditions — are exactly the constraints this algebra and its dual impose, and the design-graph dictionary is the statement that the block structures of symmetric designs land inside this algebra. The results below trace these threads and apply the association-scheme machinery of 07.05.06 rather than rebuilding it.

Theorem 1 (the Bose-Mesner algebra of an SRG). For $srg (v, k, λ, μ)$ the matrices ${A_{0}, A_{1}, A_{2}} = {I, A, J - I - A}$ form a symmetric association scheme with two classes: each $A_{i}$ is symmetric ${0, 1}$ , $\sum_{i} A_{i} = J$ , and $A_{i} A_{j} = \sum_{ℓ} p_{ij}^{ℓ} A_{ℓ}$ for intersection numbers $p_{ij}^{ℓ}$ read off $(λ, μ)$ . The algebra $A = ⟨ I, A, J ⟩$ has three primitive idempotents $E_{0} = \frac{1}{v} J$ , $E_{1}$ , $E_{2}$ projecting onto the eigenspaces for $k, r, s$ , with ranks $1, f, g$ . This is the diameter- $2$ instance of the Bose-Mesner algebra developed for general schemes in 07.05.06; the Delsarte linear-programming bound and its eigenvalue tables specialise to SRGs without further proof ^{[van Lint-Wilson Ch. 30]}.

Theorem 2 (the absolute bound). For a primitive $srg (v, k, λ, μ)$ with eigenvalue multiplicities $f, g$ , $$ v \leq \tfrac12 f(f+3) \quad\text{and}\quad v \leq \tfrac12 g(g+3) . $$ The bound comes from the Schur (entrywise) product: the idempotent $E_{1}$ has rank $f$ , and the symmetric Schur squares of its rows span a space of dimension at most $(2 f + 1)$ , while the entries of $E_{1}, E_{1} \circ E_{1}$ are forced by the scheme to be linearly independent enough to occupy $v$ dimensions; the count $v \leq (2 f + 1) + f = \frac{1}{2} f (f + 3)$ follows. Equality cases are tight extremal configurations (e.g. relating to regular two-graphs and equiangular line systems) ^{[Brouwer-Cohen-Neumaier Ch. 2]}.

Theorem 3 (the Krein conditions). The Krein parameters of the scheme, $$ q^1_{11} = \Big(1 + \frac{r^3}{f^2} \cdot \text{(scaled)} \cdots\Big) \geq 0, \qquad q^2_{22} \geq 0, $$ equivalently $(r + 1) (k + r + 2 r s) \leq (k + r) (s + 1)^{2}$ and its $r \leftrightarrow s$ partner, must hold. These are the nonnegativity of the dual intersection numbers $q_{ij}^{k}$ of the Bose-Mesner algebra (the structure constants of the idempotents under the Schur product, $E_{i} \circ E_{j} = \frac{1}{v} \sum_{ℓ} q_{ij}^{ℓ} E_{ℓ}$ ). They rule out parameter sets that pass integrality and feasibility, and equality in a Krein condition forces the graph to be a strongly regular subconstituent (a tight, often unique, configuration). The Krein machinery is the dual eigenvalue theory of association schemes from 07.05.06, applied, not re-derived ^{[Brouwer-Cohen-Neumaier Ch. 2]}.

Theorem 4 (the Hoffman-Singleton theorem). A Moore graph of diameter $2$ and girth $5$ — an $srg (k^{2} + 1, k, 0, 1)$ — exists only for $k \in {2, 3, 7, 57}$ . The eigenvalues $\frac{1}{2} (- 1 \pm 4 k - 3)$ have multiplicities that are integers only when $4 k - 3$ is rational (forcing $4 k - 3 = u^{2}$ with $u ∣ 15$ ) or when $k = 2$ . The cases $k = 2, 3, 7$ are realised by the pentagon, the Petersen graph, and the unique Hoffman-Singleton graph on $50$ vertices; existence for $k = 57$ (a graph on $3250$ vertices) is open ^{[Hoffman-Singleton 1960]}.

Theorem 5 (the design-graph dictionary). From a symmetric $2 - (v, k, λ)$ design the block graph has the $b = v$ blocks as vertices, two blocks adjacent when they meet in a prescribed number of points; for the design's standard intersection numbers this is strongly regular. Conversely, a strongly regular graph with suitable parameters reconstructs a quasi-symmetric design. The point graph and block graph of a generalised quadrangle $GQ (s, t)$ are $srg ((s + 1) (s t + 1), s (t + 1), s - 1, t + 1)$ and its dual. Latin-square graphs $L_{m} (n)$ from $m - 2$ mutually orthogonal Latin squares give $srg (n^{2}, m (n - 1), \dots)$ . The triangular graph $T (n) = L (K_{n})$ (the line graph of $K_{n}$ ) is $srg ((2 n), 2 (n - 2), n - 2, 4)$ , and the lattice (Hamming) graph $H (2, n) = K_{n} \times K_{n}$ is $srg (n^{2}, 2 (n - 1), n - 2, 2)$ ; both are characterised by their parameters except for the small exceptions ( $T (8)$ has the three Chang graphs as cospectral mates, $H (2, 4)$ has the Shrikhande graph) ^{[Cameron-van Lint Ch. 2]}.

Theorem 6 (regular two-graphs and switching). Seidel switching with respect to a vertex set $S$ complements all edges between $S$ and its complement; the Seidel matrix $S = J - I - 2 A$ changes by conjugation with a $\pm 1$ diagonal, so its spectrum is a switching invariant. A regular two-graph is a switching class whose Seidel matrix has exactly two eigenvalues; the graphs in such a class that are regular are strongly regular conference graphs, and the two-graph encodes a system of equiangular lines in $R^{f}$ . Paley graphs, conference matrices (40.06.05), and the absolute-bound equality cases meet here, linking SRGs to equiangular line systems and to Hadamard-type matrices.

Synthesis. Putting these together, every structural fact about a strongly regular graph descends from the single equation $A^{2} = k I + λ A + μ (J - I - A)$ , whose three eigenvalues ${k, r, s}$ make $⟨ I, A, J ⟩$ the smallest non-degenerate Bose-Mesner algebra: the integrality of the multiplicities $f, g$ is exactly the rationality condition, the rank constraints on the idempotents are exactly the absolute bound, and the dual structure constants are exactly the Krein conditions. This is dual to the design picture of 40.06.01, where $N N^{⊤} = (r - λ) I + λ J$ had the same two-eigenvalue form; the central insight is that pairwise common-neighbour balance and pairwise block concurrence are the same spectral phenomenon read on a graph versus on an incidence structure, and the design-graph dictionary generalises Fisher's rank- $v$ rigidity to the eigenvalue rigidity of the block graph. The bridge from these finite identities to the classification program is the association-scheme machinery of 07.05.06: the Delsarte linear-programming bound, the Krein nonnegativity, and the absolute bound are the three faces of the same dual algebra, and the Hoffman-Singleton degree restriction is the foundational reason that the locally-tree-like extremal graphs — the Moore graphs — are almost all forbidden, leaving a finite arithmetic of feasible parameter sets that the design-graph-code triangle then populates.

Full proof set Master

Proposition 1 (adjacency equation). A graph is $srg (v, k, λ, μ)$ iff $A J = k J$ and $A^{2} = k I + λ A + μ (J - I - A)$ .

Proof. The $(i, j)$ entry of $A^{2}$ is $\sum_{ℓ} A_{i ℓ} A_{ℓ j}$ , the number of common neighbours of $i$ and $j$ . For $i = j$ this is $d (i)$ , so $A_{ii}^{2} = k$ for all $i$ iff $G$ is $k$ -regular, equivalently $A J = k J$ . For $i \neq = j$ adjacent, $A_{ij}^{2}$ is the number of common neighbours, which equals $λ$ for all adjacent pairs iff that count is constant. For $i \neq = j$ non-adjacent, $A_{ij}^{2}$ equals $μ$ iff that count is constant. The matrix $k I$ supplies the diagonal $k$ ; $λ A$ supplies $λ$ at adjacent off-diagonal positions (where $A_{ij} = 1$ ); $μ (J - I - A)$ has a $1$ exactly at non-adjacent distinct pairs and supplies $μ$ there. Summing, the right-hand side reproduces $A^{2}$ entry by entry precisely when the three counts are constant, which is the definition of strong regularity. $□$

Proposition 2 (feasibility identity). $k (k - λ - 1) = (v - k - 1) μ$ .

Proof. Apply both sides of $A^{2} = k I + λ A + μ (J - I - A)$ to $1$ . Then $A^{2} 1 = k^{2} 1$ , $A 1 = k 1$ , $J 1 = v 1$ , so $k^{2} = k + λk + μ (v - 1 - k)$ . Rearranging, $k^{2} - k - λk = μ (v - 1 - k)$ , i.e. $k (k - 1 - λ) = (v - k - 1) μ$ . $□$

Proposition 3 (eigenvalues and multiplicities). $A$ has spectrum ${k^{1}, r^{f}, s^{g}}$ with $r, s = \frac{1}{2} ((λ - μ) \pm D)$ , $D = (λ - μ)^{2} + 4 (k - μ)$ , and $f, g = \frac{1}{2} ((v - 1) \mp \frac{2 k + ( v - 1 ) ( λ - μ )}{r - s})$ .

Proof. The eigenvector $1$ gives eigenvalue $k$ with multiplicity $1$ (the complement is connected, so the eigenspace for $k$ is one-dimensional). On $1^{⊥}$ the matrix $J$ acts as $0$ , so the rearranged equation $A^{2} - (λ - μ) A - (k - μ) I = μ J$ becomes $A^{2} - (λ - μ) A - (k - μ) I = 0$ ; any eigenvalue $θ \neq = k$ thus satisfies $θ^{2} - (λ - μ) θ - (k - μ) = 0$ , with the two roots $r, s$ . Writing $f, g$ for their multiplicities, $f + g = v - 1$ and (from $tr A = 0$ ) $k + f r + g s = 0$ . Solving this $2 \times 2$ linear system, with $r + s = λ - μ$ and $r - s = D$ , yields the displayed $f, g$ . $□$

Proposition 4 (rationality dichotomy). Either $D$ is a perfect square and $r, s \in Z$ , or $2 k + (v - 1) (λ - μ) = 0$ and $G$ is a conference graph $(4 t + 1, 2 t, t - 1, t)$ .

Proof. The multiplicity $f$ must be a non-negative integer. In the formula $f = \frac{1}{2} ((v - 1) - \frac{2 k + ( v - 1 ) ( λ - μ )}{D})$ , the term $\frac{2 k + ( v - 1 ) ( λ - μ )}{D}$ is either rational or irrational. If $D \in / Q$ , the only way the term is rational (as required for $f \in Z$ ) is for its numerator to vanish: $2 k + (v - 1) (λ - μ) = 0$ . Then $f = g = (v - 1) /2$ , and substituting back into the feasibility relation $k (k - 1 - λ) = (v - k - 1) μ$ with $λ - μ = - 2 k / (v - 1)$ forces $v = 2 k + 1$ , $μ = (k) /2$ requiring $k = 2 t$ , and $(λ, μ) = (t - 1, t)$ , giving $(4 t + 1, 2 t, t - 1, t)$ . If $D \in Q$ then, $D$ being an integer, $D \in Z$ , so $D$ is a perfect square and $r, s = \frac{1}{2} ((λ - μ) \pm D)$ are integers (their sum $λ - μ$ and difference $D$ have the same parity, as $λ - μ \equiv D (mod 2)$ ). $□$

Proposition 5 (friendship theorem). If every two distinct vertices of a finite graph have exactly one common neighbour, then some vertex is adjacent to all others.

Proof. Suppose, for contradiction, no such universal vertex (politician) exists. First, the "exactly one common neighbour" hypothesis forbids two distinct vertices having two common neighbours, hence forbids $C_{4}$ , and any two adjacent vertices share exactly one neighbour while any two non-adjacent share exactly one. Counting walks shows any two non-adjacent vertices have equal degree; with no politician, the non-adjacency relation is connected, so all degrees equal some $k$ , making $G = srg (v, k, 1, 1)$ . Feasibility $k (k - 2) = (v - k - 1)$ gives $v = k^{2} - k + 1$ . The restricted eigenvalues solve $x^{2} - (1 - 1) x - (k - 1) = x^{2} - (k - 1) = 0$ , so $r, s = \pm k - 1$ . The multiplicities $f, g = \frac{1}{2} ((v - 1) \mp \frac{2 k}{2 k - 1})$ are integers only if $k - 1 ∣ k$ ; since $g cd (k - 1, k) = 1$ , this forces $k - 1 = 1$ , i.e. $k = 2$ , $v = 3$ , the triangle — which has a politician (every vertex is universal). The contradiction proves a politician exists. $□$

Proposition 6 (Hoffman-Singleton degree restriction). An $srg (k^{2} + 1, k, 0, 1)$ exists only for $k \in {2, 3, 7, 57}$ .

Proof. With $λ = 0$ , $μ = 1$ , feasibility gives $k (k - 1) = (v - k - 1)$ , so $v = k^{2} + 1$ . The restricted eigenvalues solve $x^{2} + x - (k - 1) = 0$ : $r, s = \frac{1}{2} (- 1 \pm 4 k - 3)$ , and $r - s = 4 k - 3$ . The multiplicities are $f, g = \frac{1}{2} (k^{2} \mp \frac{2 k + k ^{2} \cdot 0 - \dots}{4 k - 3})$ ; concretely $g - f = \frac{2 k - k ^{2}}{4 k - 3}$ must be an integer. If $4 k - 3 \in / Z$ , integrality forces the numerator $2 k - k^{2} = 0$ , i.e. $k = 2$ . Otherwise $4 k - 3 = u^{2}$ with $u$ a positive odd integer; then $k = (u^{2} + 3) /4$ and $g - f = \frac{2 k - k ^{2}}{u}$ is an integer, so $u ∣ (2 k - k^{2})$ . Multiplying through, $u ∣ 16 (2 k - k^{2}) = - (u^{2} + 3) (u^{2} - 5) -$ a constant computation reducing to $u ∣ 15$ . Hence $u \in {1, 3, 5, 15}$ and $k = (u^{2} + 3) /4 \in {1, 3, 7, 57}$ . Excluding the degenerate $k = 1$ , the feasible degrees are ${2, 3, 7, 57}$ . $□$

Connections Master

The strongly regular graph is the spectral twin of the symmetric design of 40.06.01: where a $2$ -design carries the concurrence identity $N N^{⊤} = (r - λ) I + λ J$ with two eigenvalues, an SRG carries $A^{2} = k I + λ A + μ (J - I - A)$ with three. The block graph of a symmetric $2 - (v, k, λ)$ design is strongly regular, and the integrality of design parameters proved there generalises here to the integrality of the eigenvalue multiplicities $f, g$ — the foundational reason both objects are rigid is that a single ${0, 1}$ matrix records the combinatorial balance losslessly in its spectrum.
The Paley and Hadamard constructions of 40.06.05 supply the canonical conference graphs: the Paley graph $P (q)$ on $F_{q}$ ( $q \equiv 1 mod 4$ ) is $srg (q, \frac{q - 1}{2}, \frac{q - 5}{4}, \frac{q - 1}{4})$ in the half case, its Seidel matrix is a symmetric conference matrix, and the regular two-graphs of Theorem 6 are exactly the switching classes that the Paley conference matrices generate. This is dual to the quadratic-residue character that builds Hadamard matrices, tying SRGs into the same finite-field arithmetic.
The association-scheme and Bose-Mesner-algebra machinery of 07.05.06 is the home of the absolute bound and the Krein conditions used here: an SRG is precisely a two-class symmetric association scheme, its adjacency algebra $⟨ I, A, J ⟩$ is the diameter- $2$ Bose-Mesner algebra, and the Delsarte linear-programming bound, the Krein nonnegativity, and the rank constraints specialise from that representation-theoretic framework rather than being re-derived. The eigenvalue idempotents $E_{0}, E_{1}, E_{2}$ are the primitive idempotents of that algebra.
The design-graph-code triangle threads through the coding-theory units: the block graph and the Hoffman-Singleton degree restriction connect to the perfect-code arithmetic, and the line graphs and lattice graphs of Theorem 5 are the combinatorial substrates whose adjacency matrices double as incidence arrays. The co-produced quasi-symmetric-design unit 40.06.08 is the design half of this dictionary — quasi-symmetric $2$ -designs have strongly regular block graphs — completing the round trip from designs to graphs to the codes of 40.06.07.

Historical & philosophical context Master

Strongly regular graphs were defined by Raj Chandra Bose in 1963 (Strongly regular graphs, partial geometries and partially balanced designs, Pacific Journal of Mathematics 13), drawing the notion out of his earlier work on partially balanced incomplete block designs and the association schemes he had introduced with K. R. Nair in 1939 for the statistical analysis of agricultural experiments ^{[van Lint-Wilson Ch. 21]}. The eigenvalue method that powers the rationality condition was already implicit in this association-scheme framework, which R. C. Bose and Dale Mesner formalised as a commutative matrix algebra in 1959. The pivotal early theorem came from Alan Hoffman and Robert Singleton in 1960, who classified Moore graphs of diameter $2$ by forcing an irrational eigenvalue's multiplicity to be an integer, discovering the unique graph on $50$ vertices that bears their name and leaving the existence of a degree- $57$ Moore graph open to this day ^{[Hoffman-Singleton 1960]}.

The dual constraints — the absolute bound and the Krein conditions — were developed by Philippe Delsarte in his 1973 thesis on the linear-programming method for codes and designs and by Johan Jacob Seidel, whose study of equiangular lines and two-graphs through the Seidel matrix connected strongly regular graphs to systems of lines in Euclidean space and to conference matrices ^{[Brouwer-Cohen-Neumaier Ch. 2]}. The friendship theorem, that a graph in which every two people have exactly one common friend has a universal friend, was proved by Paul Erdős, Alfréd Rényi, and Vera Sós in 1966 by exactly the SRG eigenvalue argument. The synthesis of designs, graphs, and codes into a single subject was made explicit by Peter Cameron and Jacobus van Lint ^{[Cameron-van Lint Ch. 2]}, whose dictionary treats a symmetric design, its strongly regular block graph, and the associated code as three descriptions of one combinatorial object.

Bibliography Master

@article{bose1963strongly,
  author  = {Bose, Raj Chandra},
  title   = {Strongly regular graphs, partial geometries and partially balanced designs},
  journal = {Pacific Journal of Mathematics},
  volume  = {13},
  pages   = {389--419},
  year    = {1963}
}

@article{bosemesner1959algebraic,
  author  = {Bose, Raj Chandra and Mesner, Dale M.},
  title   = {On linear associative algebras corresponding to association schemes of partially balanced designs},
  journal = {Annals of Mathematical Statistics},
  volume  = {30},
  pages   = {21--38},
  year    = {1959}
}

@article{hoffmansingleton1960moore,
  author  = {Hoffman, Alan J. and Singleton, Robert R.},
  title   = {On Moore graphs with diameters 2 and 3},
  journal = {IBM Journal of Research and Development},
  volume  = {4},
  pages   = {497--504},
  year    = {1960}
}

@article{erdosrenyisos1966friendship,
  author  = {Erd\H{o}s, Paul and R\'enyi, Alfr\'ed and S\'os, Vera T.},
  title   = {On a problem of graph theory},
  journal = {Studia Scientiarum Mathematicarum Hungarica},
  volume  = {1},
  pages   = {215--235},
  year    = {1966}
}

@phdthesis{delsarte1973algebraic,
  author  = {Delsarte, Philippe},
  title   = {An algebraic approach to the association schemes of coding theory},
  school  = {Universit\'e Catholique de Louvain},
  year    = {1973},
  note    = {Philips Research Reports Supplements 10}
}

@book{brouwercohenneumaier1989distance,
  author    = {Brouwer, Andries E. and Cohen, Arjeh M. and Neumaier, Arnold},
  title     = {Distance-Regular Graphs},
  publisher = {Springer-Verlag},
  series    = {Ergebnisse der Mathematik und ihrer Grenzgebiete},
  year      = {1989}
}

@book{brouwerhaemers2012spectra,
  author    = {Brouwer, Andries E. and Haemers, Willem H.},
  title     = {Spectra of Graphs},
  publisher = {Springer},
  series    = {Universitext},
  year      = {2012}
}

@book{godsilroyle2001algebraic,
  author    = {Godsil, Chris and Royle, Gordon},
  title     = {Algebraic Graph Theory},
  publisher = {Springer},
  series    = {Graduate Texts in Mathematics},
  volume    = {207},
  year      = {2001}
}

@book{cameronvanlint1991designs,
  author    = {Cameron, Peter J. and van Lint, Jacobus H.},
  title     = {Designs, Graphs, Codes and their Links},
  publisher = {Cambridge University Press},
  series    = {London Mathematical Society Student Texts},
  volume    = {22},
  year      = {1991}
}

@book{vanlintwilson2001course,
  author    = {van Lint, J. H. and Wilson, R. M.},
  title     = {A Course in Combinatorics},
  edition   = {2},
  publisher = {Cambridge University Press},
  year      = {2001}
}

Prerequisites

40.06.01

Tier anchors

beginner: van Lint-Wilson 2001 *A Course in Combinatorics* 2e (Cambridge) Ch. 21 (strongly regular graphs by hand: a regular graph where adjacent pairs share a fixed number of common neighbours and non-adjacent pairs share another; the Petersen graph as the picture-perfect example); Cameron-van Lint 1991 *Designs, Graphs, Codes and their Links* (Cambridge) Ch. 2 for the friendly small examples
intermediate: van Lint-Wilson 2001 *A Course in Combinatorics* 2e (Cambridge) Ch. 21 (the parameters $(v,k,\lambda,\mu)$, the adjacency-matrix equation $A^2 = kI + \lambda A + \mu(J - I - A)$, the eigenvalues $k, r, s$ and their multiplicities $f, g$, the rationality/integrality conditions and conference graphs); Brouwer-Haemers 2012 *Spectra of Graphs* (Springer) Ch. 9; Godsil-Royle 2001 *Algebraic Graph Theory* (Springer GTM 207) Ch. 10
master: van Lint-Wilson 2001 *A Course in Combinatorics* 2e Ch. 21 and Ch. 30 (strongly regular graphs, the absolute bound, association schemes); Brouwer-Cohen-Neumaier 1989 *Distance-Regular Graphs* (Springer) Ch. 1-3 (SRGs as the diameter-2 case, the Krein conditions, the absolute bound); Brouwer-Haemers 2012 *Spectra of Graphs* (Springer) Ch. 9; Hoffman-Singleton 1960 *IBM J. Res. Develop.* 4 (Moore graphs of diameter 2); Seidel 1968 (regular two-graphs and equiangular lines)

References

van Lint, J. H. & Wilson, R. M. — A Course in Combinatorics · Cambridge University Press, 2nd edition (2001). Chapter 21 develops strongly regular graphs: a $k$-regular graph on $v$ vertices in which adjacent vertices have $\lambda$ common neighbours and non-adjacent vertices have $\mu$ common neighbours, the adjacency-matrix identity $A^2 = kI + \lambda A + \mu(J - I - A)$, the eigenvalues $k$ and the two roots $r, s$ of $x^2 - (\lambda - \mu)x - (k - \mu) = 0$ with multiplicities $f, g$, the integrality (rationality) condition forcing either the half case ($f = g$, conference graphs) or integer eigenvalues, and examples including the Petersen graph, Paley graphs, triangular and lattice graphs; Chapter 30 places SRGs inside the theory of association schemes and the Bose-Mesner algebra.
Hoffman, A. J. & Singleton, R. R. — On Moore graphs with diameters 2 and 3 · IBM Journal of Research and Development 4 (1960), 497-504. The proof that a regular graph of diameter $2$ and girth $5$ (a Moore graph: $\mu = 1$, $\lambda = 0$) can have degree only $2, 3, 7$, or $57$, obtained by forcing the multiplicity of an irrational eigenvalue to be an integer; the pentagon, the Petersen graph, and the Hoffman-Singleton graph realise the first three, the degree-$57$ case is open.
Brouwer, A. E., Cohen, A. M. & Neumaier, A. — Distance-Regular Graphs · Springer-Verlag (1989). Chapters 1-3 treat strongly regular graphs as the diameter-$2$ distance-regular graphs: the parameter feasibility conditions, the eigenvalue multiplicities, the Krein conditions (nonnegativity of the Krein parameters $q^k_{ij}$ of the association scheme), and the absolute bound $v \leq \tfrac12 f(f+3)$ and $v \leq \tfrac12 g(g+3)$ relating $v$ to the multiplicities, with the standard tables of feasible parameter sets.
Godsil, C. & Royle, G. — Algebraic Graph Theory · Springer Graduate Texts in Mathematics 207 (2001). Chapter 10 develops strongly regular graphs from the adjacency algebra: the quadratic $A^2 = kI + \lambda A + \mu(J-I-A)$, the three-dimensional Bose-Mesner algebra $\langle I, A, J\rangle$, eigenvalue interlacing, the rationality conditions and conference graphs, the friendship theorem, and the constructions from symmetric $2$-designs, Latin squares, and regular two-graphs.
Cameron, P. J. & van Lint, J. H. — Designs, Graphs, Codes and their Links · Cambridge University Press, London Mathematical Society Student Texts 22 (1991). A unified treatment of the design-graph-code triangle: strongly regular graphs from the block graphs and point graphs of $2$-designs, from quadratic residues (Paley graphs), from generalised quadrangles, and from regular two-graphs and Seidel switching; the dictionary translating a symmetric $2$-$(v,k,\lambda)$ design into the strongly regular block graph of its blocks.

Estimated time

beginner: 18m
intermediate: 46m
master: 88m