This follows by unfolding the definition of \(X(S)_1 = E(G) \cap S^{(2)}\) and applying the characterisation of membership in \(S^{(2)}\): by simplification, \(e \in E(G) \cap S^{(2)}\) if and only if \(e \in E(G)\) and every vertex of \(e\) lies in \(S\).

From the hypothesis, obtain \(e \in E(G)\) with \(\forall v \in e,\, v \in S\). Then \(e \in X(S)_1\) by the membership characterisation (Lemma 306), so \(X(S)_1\) is nonempty.

We unfold the dot product and matrix-vector multiplication using the definitions of \(\mathbf{1}_S\) and \(M\):

Step 1. Since \(M_{vw} = \mathbf{1}[G.Adj(v,w)]\) and \(\mathbf{1}_S(v), \mathbf{1}_S(w) \in \{ 0,1\} \), the double sum simplifies to

Step 2. By rewriting via the indicator function of the filtered product set, this equals the cardinality

Step 3. We exhibit a \(2\)-to-\(1\) map from these ordered pairs to unordered induced edges: by the symmetry of adjacency, each unordered edge \(\{ v,w\} \in X(S)_1\) corresponds to exactly two ordered pairs \((v,w)\) and \((w,v)\) with \(v \neq w\). Concretely, for each \(e = s(v,w) \in X(S)_1\) the fibre \(\{ (a,b) : G.\operatorname {Adj}(a,b) \land a \in S \land b \in S \land s(a,b) = e\} \) equals \(\{ (v,w),(w,v)\} \), which has cardinality \(2\) since \(v \neq w\) (graphs have no self-loops). Partitioning the filtered product by edge and applying the constant-fibre sum formula gives the total count \(= 2\, |X(S)_1|\). Simplification by ring arithmetic concludes.

We use the handshaking lemma \(\sum _{v \in V} \deg (v) = 2|E(G)|\). Since \(G\) is \(s\)-regular, \(\deg (v) = s\) for all \(v\), so \(\sum _{v}\deg (v) = s\, |V|\). Substituting and casting to \(\mathbb {R}\) gives \(2|E(G)| = s|V|\).

Let \(U\) be the eigenvector unitary (orthogonal matrix) with \(A = U D U^\top \) (spectral theorem for real Hermitian matrices), where \(D = \operatorname {diag}(\lambda _j)\).

Step 1. We verify \(\star U = U^\top \) using that \(A\) is real Hermitian.

Step 2. Set \(y = U^\top x\). Then \(Ax = U(Dy)\) by associativity.

Step 3. Compute \(x^\top (Ax) = x^\top U (D y)\). Since \(\operatorname {vecMul}(x, U) = U^\top x = y\) (by expanding definitions of vector multiplication and transposition for real matrices), we get \(x^\top A x = y^\top D y\).

Step 4. Since \(D\) is diagonal, \(y^\top D y = \sum _j \lambda _j y_j^2\).

Step 5. Observe that \(y_j = (U^\top x)_j = \sum _i x_i U_{ij} = x \cdot v_j\) where \(v_j\) is the \(j\)-th eigenvector. Rewriting using \(U_{ij} = (v_j)_i\) and collecting terms gives the result.

Let \(U\) be the eigenvector unitary. We first show \(\| x\| ^2 = \| y\| ^2\) where \(y = U^\top x\). Indeed, by the orthogonality identity \(UU^\top = I\) (from the unitary property and \(\star U = U^\top \)):

computed via the chain \(\| y\| ^2 = \operatorname {vecMul}(U^\top x, U^\top ) \cdot x = U(U^\top x) \cdot x = (UU^\top x) \cdot x = x \cdot x\). Then \(\| y\| ^2 = \sum _j y_j^2\), and since \(y_j = x \cdot v_j\), this gives \(\| x\| ^2 = \sum _j (x\cdot v_j)^2\).

Rewrite using the spectral decomposition (Lemma 311) and Parseval identity (Lemma 312):

where the inequality uses \(\lambda _j \leq C\) and \((x\cdot v_j)^2 \geq 0\) term by term.

Let \(v = v_j\) be the \(j\)-th orthonormal eigenvector. By the Rayleigh quotient characterisation, \(\lambda _j = v^\top A v\) (since \(\| v\| = 1\)). We bound \(v^\top Av\) by the AM–GM inequality.

Since \(G\) is \(s\)-regular, the adjacency matrix satisfies \(A_{pq} = \mathbf{1}[G.\operatorname {Adj}(p,q)]\) and \(\sum _q \mathbf{1}[G.\operatorname {Adj}(p,q)] = s\) for all \(p\).

Unit norm. The orthonormality of the eigenvector basis gives \(v^\top v = \sum _i v_i^2 = 1\) (after converting the Euclidean norm condition \(\| v\| = 1\) via \(\sqrt{\sum _i |v_i|^2} = 1\)).

AM–GM bound. For all \(a, b \in \mathbb {R}\): \(ab \leq (a^2 + b^2)/2\) (since \((a-b)^2 \geq 0\)). Therefore

Splitting the sum: \(\sum _p\sum _q \mathbf{1}[G.\operatorname {Adj}(p,q)] v_p^2/2 = (s/2)\sum _p v_p^2\) by regularity, and symmetrically for the \(v_q^2\) terms (using \(G.\operatorname {Adj}(p,q) \Leftrightarrow G.\operatorname {Adj}(q,p)\)). Thus the bound equals \(s\sum _p v_p^2 = s\). Since \(v^\top v = 1\), we obtain \(\lambda _j = v^\top Av \leq s\).

We show \((s : \mathbb {R})\) lies in the spectrum of \(A(G)\) by proving it is not in the resolvent. Assume for contradiction that \(sI - A\) is invertible. The all-ones vector \(\mathbf{1} : V \to \mathbb {R}\) is in the kernel of \(sI - A\): for each \(v\),

by regularity. Since \(\mathbf{1} \neq 0\) (it evaluates to \(1\) at any vertex), injectivity of \(sI - A\) is contradicted. Hence \(s \in \operatorname {Spec}(A(G))\), and by the spectral theorem for real Hermitian matrices this coincides with the range of the eigenvalue function.

Let \(\lambda _1 = \operatorname {adjEigenvalues}(G)\langle 0, \cdot \rangle \) (the largest eigenvalue in descending order).

Upper bound \(\lambda _1 \leq s\): Express \(\lambda _1\) in terms of the Hermitian eigenvalue function and apply Lemma 314.

Lower bound \(s \leq \lambda _1\): By \(|V| \geq 2\) the graph is nonempty, so by Lemma 315 there exists an index \(j\) with \(\lambda _j = s\). Expressing \(\lambda _j\) via the equivalence from \(\operatorname {Fin}(|V|)\) and using the antitone property \(\lambda _k \leq \lambda _1\) for all \(k\) (Lemma 241), we get \(s = \lambda _j \leq \lambda _1\).

Combining, \(\lambda _1 = s\).

Expanding the dot product and using that \(\mathbf{1}_S(v)^2 = \mathbf{1}_S(v)\) (since values are \(0\) or \(1\)), we obtain \(\sum _{v \in V} \mathbf{1}_S(v) = |S \cap V| = |S|\) by the boolean sum formula.

For each \(v \in V\): \((A(G)\mathbf{c})_v = \sum _w A_{vw} c = c \sum _w \mathbf{1}[G.\operatorname {Adj}(v,w)] = c\cdot s = sc\) by regularity. Hence \(A(G)\mathbf{c} = sc\, \mathbf{1}\).

Since \(x_v = \gamma + z_v\), we compute \(A(G)x\) using linearity and Lemma 318: \((A(G)x)_v = s\gamma + (A(G)z)_v\). Expanding the quadratic form:

Summing term by term:

• \(\sum _v s\gamma ^2 = s\gamma ^2|V|\).

• \(\sum _v \gamma (Az)_v = \gamma \sum _v(Az)_v = \gamma \cdot s\sum _v z_v = 0\), since \(\sum _v (Az)_v = \sum _v\sum _w A_{vw}z_w = \sum _w z_w\sum _v A_{vw} = s\sum _w z_w = 0\) using symmetry of adjacency and regularity, together with \(\sum _v z_v = 0\).

• \(\sum _v s\gamma z_v = s\gamma \sum _v z_v = 0\).

• \(\sum _v z_v(Az)_v = z^\top Az\).

Therefore \(x^\top Ax = s\gamma ^2|V| + z^\top Az\).

orange[Uses unproven axiom: thm:AlonChung.regular_eigenvector_s_constant]

Set \(z_v = \mathbf{1}_S(v) - \gamma \). Since \(n {\gt} 0\) and \(\gamma = |S|/n\):

Write \(\mathbf{1}_S = \gamma \mathbf{1} + z\). By the quadratic decomposition (Lemma 319):

It suffices to show \(z^\top Az \leq \lambda _2\, \| z\| ^2\), since \(\| z\| ^2 = \gamma (1-\gamma )n\) (computed by expanding \(\sum _v(1_S(v)-\gamma )^2 = |S| - 2\gamma |S| + n\gamma ^2 = \gamma (1-\gamma )n\)).

We use the spectral decomposition (Lemma 311) and Parseval (Lemma 312):

We need \(\sum _j \lambda _j c_j^2 \leq \lambda _2 \sum _j c_j^2\) where \(c_j = z\cdot v_j\).

Case 1: All eigenvalues \(\leq \lambda _2\). Then term by term \(\lambda _j c_j^2 \leq \lambda _2 c_j^2\), so the sum inequality holds.

Case 2: Some eigenvalue \({\gt} \lambda _2\). This forces a gap \(\lambda _1 {\gt} \lambda _2\). For each \(j\):

• If \(\lambda _j \leq \lambda _2\): \(\lambda _j c_j^2 \leq \lambda _2 c_j^2\).

• If \(\lambda _j {\gt} \lambda _2\): By the antitone ordering of eigenvalues and the gap, \(j\) must correspond to index \(0\) (the largest), i.e. \(\lambda _j = \lambda _1 = s\) (Lemma 316). The eigenvector \(v_j\) satisfies \(A v_j = s\, v_j\), and by the axiom (Theorem 320), \(v_j = c\mathbf{1}\) for some constant \(c\). Then \(z\cdot v_j = c\sum _v z_v = 0\), so \(c_j = 0\) and \(\lambda _j c_j^2 = 0 \leq \lambda _2 c_j^2\).

Summing over all \(j\) gives \(z^\top Az \leq \lambda _2\| z\| ^2\), completing the proof.

orange[Uses unproven axiom: thm:AlonChung.regular_eigenvector_s_constant]

Step 1. By the quadratic form identity (Lemma 309):

Step 2. By the spectral bound (Lemma 321):

Combining Steps 1 and 2 by linear arithmetic:

Step 3. By the edge count formula (Lemma 310): \(2|E(G)| = sn\), so \(|E(G)| = sn/2\).

Step 4. We expand \(\alpha \, |E(G)|\):

where the field simplification uses \(s {\gt} 0\). Combining with Step 2 and \(n {\gt} 0\), \(s {\gt} 0\):