To address the problem, we will first establish the quadratic form identity for the adjacency matrix of a graph and then use this identity to derive the edge count for a subset of vertices.

Let G = (V, E) be a simple, undirected, connected, d-regular graph on n vertices. The adjacency matrix A of the graph is defined such that the entry A_u,v is 1 if there is an edge between vertices u and v, and 0 otherwise.

The eigenvalues of the adjacency matrix A are denoted as:

• d = λ₁ ≥ λ₂ ≥ ... ≥ λ_n ≥ -d

We define:

• λ = max{|λ₂|, |λ_n|} (the spectral radius off the trivial eigenvalue).

For a vertex subset S ⊆ V, let e(S, S) denote the number of edges with both endpoints in S.

Quadratic Form Identity

We need to show that for any vector x ∈ ℝⁿ, the following holds:

x^⊤A x = ∑_{(u,v) ∈ E} 2 x_ux_v.

To prove this, let x = (x₁, x₂, ..., x_n) be a vector in ℝⁿ. The expression x^⊤A x can be expanded as follows:

x⊤A x = Σu=1n Σv=1n xuxvAu,v.

Since A_u,v = 1 if there is an edge between u and v and 0 otherwise, we can rewrite this as:

x⊤A x = Σ(u,v) ∈ E xuxv + Σ(v,u) ∈ E xuxv = Σ(u,v) ∈ E 2 xuxv.

This establishes the quadratic form identity. Now, let’s use this identity to derive the edge count for a subset of vertices.

Edge Count for a Subset

Let S be a subset of vertices in V. The indicator vector for S is defined as:

1S = (1s1, 1s2, ..., 1sn),

where 1_si = 1 if vertex i is in S and 0 otherwise.

Using the quadratic form identity, we can write:

1S⊤A1S = Σ(u,v) ∈ E 2 1Su1Sv.

Here, 1_Su = 1 if u ∈ S and 1_Sv = 1 if v ∈ S. Thus, the summation counts each edge in E twice if both endpoints are in S. Therefore:

e(S, S) = 1/2 1_S^⊤A1_S.

In conclusion, we have established the quadratic form identity and demonstrated how it can be used to compute the number of edges within a subset of vertices in a regular graph. This result is fundamental in spectral graph theory and has applications in various fields, including network analysis and combinatorial optimization.

For further reading, you may refer to:

• Godsil, C. D., & Royle, G. (2001). Algebraic Graph Theory. Springer.
• Chung, F. R. K. (1997). Spectral Graph Theory. American Mathematical Society.