What can a graph's eigenvalues reveal about its combinatorial shape?
A matrix turns local adjacency into a linear operator. Its eigenvalues can then certify connectedness, count closed walks, bound independent sets, and control cuts. The challenge is choosing the correct matrix and hypotheses: an adjacency eigenvalue, a Laplacian eigenvalue, and a normalized Laplacian eigenvalue have different meanings.
For the chapter foundation, all graphs are finite, simple, undirected, and unweighted. The adjacency matrix $A$ has entry one exactly on adjacent vertex pairs. The degree matrix $D$ is diagonal, and $L=D-A$ is the Laplacian. Its kernel consists of vectors constant on each connected component. For a $d$-regular graph, order adjacency eigenvalues as $d=\lambda_1\geq\lambda_2\geq\cdots\geq\lambda_n$. The Laplacian eigenvalues are $d-\lambda_i$, and the normalized Laplacian eigenvalues are $\mu_i=1-\lambda_i/d$, in increasing order when $d\gt0$.
Two established tools will support the final investigation. For a regular graph with an edge and least adjacency eigenvalue $\tau\lt0$, Hoffman's bound is $\alpha(G)\leq n(-\tau)/(d-\tau)$, where $\alpha$ is the maximum independent-set size. For a connected regular graph, conductance $\Phi$ satisfies $\mu_2/2\leq\Phi\leq\sqrt{2\mu_2}$, using the definition in 31.5. The optional sections give proofs and further applications; their advanced arguments are not required to complete the foundation investigation.
What can a graph's eigenvalues reveal about its combinatorial shape?
Use the Petersen graph in its two-subset model. Its vertices are $12,13,14,15,23,24,25,34,35,45$, where $ab$ denotes $\{a,b\}$. Join two vertices exactly when their two-subsets are disjoint. Every vertex has three neighbors; for example $12$ is adjacent to $34,35,45$.
The graph has ten vertices and fifteen edges. Adjacent vertices have no common neighbor, while nonadjacent distinct vertices have exactly one. Consequently
$$ A^2=2I-A+J, $$
where $J$ is the all-ones matrix. On the constant vector, $A$ has eigenvalue three. On its orthogonal complement, $J$ vanishes, so every eigenvalue solves $x^2+x-2=0$, giving $1$ or $-2$. The multiplicities, found from dimension and trace, are five and four. Thus the adjacency spectrum is $3,1^{[5]},(-2)^{[4]}$, where brackets denote multiplicity.
Hoffman's bound now gives $\alpha\leq10\cdot2/(3+2)=4$. The vertices $12,13,14,15$ have pairwise intersecting labels, hence are pairwise nonadjacent: they attain four. A matrix certificate and a concrete set together prove $\alpha=4$. Revisit why the least eigenvalue constrains an independent set, and why a numerical spectrum alone needs an exact justification before it certifies an integer bound.
31.1 Adjacency, Laplacian, and incidence matrices
Optional extension; not required to complete the chapter foundation. Adjacency measures propagation; the Laplacian measures variation across edges. An incidence factorization explains why the latter is positive semidefinite.
Give each edge an arbitrary orientation. The signed vertex-edge incidence matrix $B$ has a column with $-1$ at its tail, $+1$ at its head, and zeros elsewhere. Each edge contributes one to the two diagonal entries and minus one to the corresponding off-diagonal entries, proving
$$ L=BB^{\mathsf T},\qquad x^{\mathsf T}Lx=\sum_{\{u,v\}\in E}(x_u-x_v)^2\geq0. $$
Reversing an edge negates its column and leaves $BB^{\mathsf T}$ unchanged. This identity proves that $Lx=0$ exactly when $x$ is constant on each connected component, so the nullity counts components. The unsigned incidence matrix instead satisfies $BB^{\mathsf T}=D+A$; orientation and sign conventions cannot be omitted.
When all degrees are positive, define the symmetric normalized Laplacian and random-walk matrix by
$$ \mathcal L=I-D^{-1/2}AD^{-1/2},\qquad P=D^{-1}A. $$
They are related by similarity between $P$ and $D^{-1/2}AD^{-1/2}$. Isolated vertices require a separately specified convention; this chapter's normalized statements exclude them. For nonregular graphs, $L$ is not a scalar multiple of $\mathcal L$, and adjacency eigenvalues cannot simply be subtracted from one fixed degree.
Solved example. For the path $1-2-3$, orient edges $1\to2$ and $2\to3$:
$$ A=\begin{pmatrix}0&1&0\\1&0&1\\0&1&0\end{pmatrix},\quad B=\begin{pmatrix}-1&0\\1&-1\\0&1\end{pmatrix},\quad L=\begin{pmatrix}1&-1&0\\-1&2&-1\\0&-1&1\end{pmatrix}. $$
The adjacency spectrum is $\sqrt2,0,-\sqrt2$. The Laplacian eigenvectors $(1,1,1)$, $(1,0,-1)$, and $(1,-2,1)$ have eigenvalues $0,1,3$. The normalized Laplacian has spectrum $0,1,2$. These differences illustrate why normalization matters.
The entry $(A^k)_{uv}$ counts walks of length $k$ from $u$ to $v$: induction appends the last edge. In particular $\operatorname{tr}(A^2)=2\lvert E\rvert$ and $\operatorname{tr}(A^3)=6$ times the number of triangles. These are walk counts, not generally counts of simple cycles for larger $k$.
Use signed incidence for $L=BB^{\mathsf T}$, and distinguish $L$ from $\mathcal L$. The adjacency-to-Laplacian shift $d-\lambda_i$ is valid for regular graphs; normalized formulas here require positive degrees.
Exercise. Reverse the first path edge and recompute $BB^{\mathsf T}$. Also determine the Laplacian nullity after adjoining one isolated vertex. Hint: A column sign cancels in the outer product. Solution: The first column becomes $(1,-1,0)^{\mathsf T}$, and the product is the same $L$. The extra isolated vertex contributes a zero block, so nullity becomes two, matching the two connected components.
31.2 Eigenvalue interlacing
Optional extension; not required to complete the chapter foundation. Restricting a symmetric matrix to a coordinate subspace cannot create completely unconstrained eigenvalues. The variational principle makes this precise.
Let a real symmetric $n\times n$ matrix $M$ have decreasing eigenvalues $\lambda_1\geq\cdots\geq\lambda_n$. If $N$ is an $m\times m$ principal submatrix with decreasing eigenvalues $\theta_1\geq\cdots\geq\theta_m$, then
$$ \lambda_i\geq\theta_i\geq\lambda_{i+n-m},\qquad1\leq i\leq m. $$
More generally this holds for the compression $Q^{\mathsf T}MQ$ when $Q^{\mathsf T}Q=I_m$. The Courant–Fischer principle characterizes eigenvalues by maximizing and minimizing the Rayleigh quotient $x^{\mathsf T}Mx/x^{\mathsf T}x$ over subspaces. Restricting those subspaces to $\operatorname{im}Q$ gives the first inequality; its codimension $n-m$ gives the shifted second inequality. This is the proof mechanism, with the standard min–max theorem as a linear-algebra prerequisite.
For an induced subgraph, adjacency is a principal submatrix. Its Laplacian usually is not the corresponding principal submatrix of the original Laplacian: deleted edges change the retained degrees. Confusing these two operations gives incorrect interlacing arguments.
Eigenvalue interlacing: a worked example
Delete one vertex from the four-cycle $C_4$. The resulting induced graph is the path $P_3$. The adjacency spectra are $2,0,0,-2$ and $\sqrt2,0,-\sqrt2$ respectively. Here $n=4,m=3$, so every required inequality is
$$ 2\geq\sqrt2\geq0,\qquad 0\geq0\geq0,\qquad 0\geq-\sqrt2\geq-2. $$
The matrices are real symmetric, and the path adjacency is literally a principal submatrix, so all hypotheses hold. The middle equality checks the repeated eigenvalue correctly; one must retain multiplicities when ordering a spectrum.
For a second compression, partition Petersen vertices into $S=\{12,13,14,15\}$ and its six-vertex complement. Every vertex in $S$ has three neighbors outside; every outside vertex has two in $S$ and one outside. The quotient is $\begin{pmatrix}0&3\\2&1\end{pmatrix}$. It is not symmetric, but using normalized cell indicators gives the symmetric compression
$$ Q^{\mathsf T}AQ=\begin{pmatrix}0&\sqrt6\\\sqrt6&1\end{pmatrix}, $$
with eigenvalues three and minus two. Because the neighbor counts are constant on each cell, this partition is equitable; cell-constant vectors form an invariant subspace, so these eigenvalues lift to actual adjacency eigenvalues. Merely averaging neighbor counts for a nonequitable partition would give interlacing, without that lifting conclusion.
Exercise. Delete an endpoint from $P_3$ and check interlacing for the resulting single edge. Hint: Its eigenvalues are $1,-1$. Solution: $\sqrt2\geq1\geq0$ and $0\geq-1\geq-\sqrt2$. Its Laplacian is $\begin{pmatrix}1&-1\\-1&1\end{pmatrix}$, whereas the retained principal block of the original path Laplacian is $\begin{pmatrix}2&-1\\-1&1\end{pmatrix}$ after deleting vertex one. These are different matrices.
31.3 Spectral graph bounds
Optional extension; not required to complete the chapter foundation. A spectral inequality becomes useful when paired with a combinatorial witness and a clear direction of comparison.
For any graph with $n$ vertices, $m$ edges, and maximum degree $\Delta$, the largest adjacency eigenvalue satisfies
$$ \frac{2m}{n}\leq\lambda_1\leq\Delta. $$
The lower bound uses the all-ones vector in the Rayleigh quotient. For the upper bound, take an eigenvector and a coordinate of largest absolute value: $\lvert\lambda\rvert\lvert x_u\rvert\leq d(u)\max_v\lvert x_v\rvert\leq\Delta\lvert x_u\rvert$. This bounds every eigenvalue's absolute value. In a regular graph both sides agree at $d$. If a graph contains a clique of size $r$, its induced adjacency has largest eigenvalue $r-1$, so interlacing gives $\omega(G)\leq\lambda_1+1$.
Solved example. Petersen is cubic, so $\lambda_1=3$ and the clique bound gives $\omega\leq4$, a weak estimate. Its spectral triangle count is
$$ 6t=\operatorname{tr}(A^3)=3^3+5\cdot1^3+4\cdot(-2)^3=0. $$
Thus there are no triangles, improving the clique bound to $\omega\leq2$. Any edge witnesses $\omega=2$. Its edge count also checks spectrally: $(3^2+5\cdot1^2+4\cdot(-2)^2)/2=15$.
Hoffman's independent-set bound, stated in the foundation and proved in 31.9, gives another exact conclusion: $\alpha\leq4$, attained by all two-subsets containing one fixed label. The figure highlights this witness. Every drawn edge joins disjoint two-subsets; geometric line crossings are not vertices. This makes the spectral certificate and the finite object directly comparable.
Spectra also have limits. The connected star $K_{1,4}$ and the disconnected graph $C_4\sqcup K_1$ share adjacency spectrum $2,0,0,0,-2$. Their independent-set sizes are four and three. Thus adjacency spectrum alone does not determine connectedness or independence in general. Laplacian nullity distinguishes their component counts. For a regular graph, however, the multiplicity of adjacency eigenvalue $d$ does count components, because $L=dI-A$.
Exercise. Use the complement to obtain another clique bound for Petersen. Hint: The complement is six-regular, and on vectors perpendicular to $\mathbf1$ its eigenvalues are $-1-\lambda_i$. Solution: Its spectrum is $6,(-2)^{[5]},1^{[4]}$. Hoffman's bound gives $\alpha(\overline G)\leq10\cdot2/(6+2)=5/2$. Since the left side is an integer, $\omega(G)\leq2$, attained by an edge. Rounding and the direction of the inequality are essential.
31.4 Expander graphs
Optional extension; not required to complete the chapter foundation. Expansion means that small vertex sets have many connections leaving them. It measures resistance to bottlenecks, rather than merely the presence of a path between every pair.
For a $d$-regular graph, let $\partial S$ consist of edges with exactly one endpoint in $S$ and define
$$ h(G)=\min_{0\lt\lvert S\rvert\leq n/2}\frac{\lvert\partial S\rvert}{\lvert S\rvert}. $$
A bounded-degree expander family has increasing numbers of vertices and a uniform positive lower bound on $h$. A single small graph can illustrate expansion, but is not itself an infinite family. Vertex expansion is a different measure; bounded degree lets one compare the two because each outside vertex is incident to at most $d$ boundary edges.
For connected regular graphs, the one-sided normalized gap is $\mu_2=(d-\lambda_2)/d$. The absolute nonprincipal adjacency parameter is
$$ \Lambda=\max_{2\leq i\leq n}\lvert\lambda_i\rvert. $$
The first controls cuts through Cheeger inequalities; the second controls signed fluctuations and nonlazy random walks. A connected bipartite graph has eigenvalue $-d$, so $\Lambda=d$ even when its one-sided gap is large. These quantities must not both be called an unspecified “second eigenvalue.”
Solved example. For Petersen, $\mu_2=2/3$, $\Lambda=2$, and $h=1$, as established in 31.5. To remove periodicity issues, use the lazy random walk
$$ P_{\mathrm{lazy}}=\frac12(I+A/d). $$
Its nonconstant eigenvalues are $1-\mu_i/2$, all in $[0,1)$ for a connected graph. The uniform distribution $\pi$ is stationary. Spectral contraction on the zero-sum subspace and Cauchy–Schwarz give, from any starting vertex,
$$ \lVert p_t-\pi\rVert_{\mathrm{TV}} \leq\frac{\sqrt{n-1}}2(1-\mu_2/2)^t. $$
Indeed the initial Euclidean distance from uniform is $\sqrt{1-1/n}$, it contracts by the displayed eigenvalue factor, and total variation is half the $\ell^1$ distance, at most $\sqrt n/2$ times the Euclidean distance. For Petersen the eigenvalues of this walk are $1,(2/3)^{[5]},(1/6)^{[4]}$. At ten steps the bound is $(3/2)(2/3)^{10}\lt0.027$.
In contrast, the cycle $C_N$ has a consecutive set of $\lfloor N/2\rfloor$ vertices with only two boundary edges. Thus $h(C_N)\leq2/\lfloor N/2\rfloor\to0$: cycles do not form an expander family. Their normalized gap $1-\cos(2\pi/N)$ likewise tends to zero.
Exercise. Explain why the ordinary walk on $C_4$ fails to converge from a vertex although $\mu_2=1$. Hint: Its adjacency spectrum contains $-2$. Solution: The walk alternates the two bipartition classes, so a parity component persists. The lazy walk has spectrum $1,1/2,1/2,0$ and converges. The one-sided gap alone did not remove the nonlazy eigenvalue minus one.
31.5 Cheeger inequalities
Optional extension; not required to complete the chapter foundation. For a connected graph with positive degrees, let $\operatorname{vol}(S)=\sum_{v\in S}d(v)$ and define conductance by
$$ \Phi(G)=\min_{\varnothing\neq S\subsetneq V} \frac{\lvert\partial S\rvert}{\min(\operatorname{vol}(S),\operatorname{vol}(V\setminus S))}. $$
If $\mu_2$ is the second-smallest eigenvalue of $\mathcal L$, the standard Cheeger inequalities are $\mu_2/2\leq\Phi\leq\sqrt{2\mu_2}$. In a regular graph $\Phi=h/d$. The following proof treats that case in full; the general case uses degree-weighted means and norms. See Chung's treatment of isoperimetric problems for that weighted formulation.
Lower bound. For a set of size $s\leq n/2$, use $x=\mathbf1_S-(s/n)\mathbf1$, perpendicular to constants. Its energy is $\lvert\partial S\rvert$ and its squared norm is $s(1-s/n)$. The variational characterization gives
$$ \mu_2\leq\frac{\lvert\partial S\rvert}{d\,s(1-s/n)} \leq\frac{2\lvert\partial S\rvert}{ds}. $$
Minimizing over sets proves $\mu_2/2\leq\Phi$.
Upper bound and sweep mechanism. Take a nonzero real eigenvector $f$ satisfying $Lf=d\mu_2 f$ and $\sum_v f_v=0$. Choose a median $m$, so both strict sides contain at most $n/2$ vertices. If $m\leq0$, put $g=(f-m)_+$; if $m\geq0$, put $g=(m-f)_+$. Choose either branch when $m=0$. The chosen $g$ is nonzero and supported on at most half the vertices.
For the first branch, monotonicity of truncation gives
$$ \sum_{uv\in E}(g_u-g_v)^2 \leq\sum_{uv\in E}(g_u-g_v)(f_u-f_v) =g^{\mathsf T}Lf =d\mu_2\left(\sum_vg_v^2+m\sum_vg_v\right) \leq d\mu_2\sum_vg_v^2. $$
The second branch uses $-f$ and $-m$, giving the same result. This explicitly justifies the truncation step.
For thresholds $t\geq0$, let $S_t=\{v:g_v^2\gt t\}$. Integrating the boundary and size of these level sets gives
$$ \int_0^\infty\lvert\partial S_t\rvert\,dt =\sum_{uv\in E}\lvert g_u^2-g_v^2\rvert,\qquad \int_0^\infty d\lvert S_t\rvert\,dt=d\sum_vg_v^2. $$
Thus at least one nonempty level set has conductance at most the ratio of the two right sides. Cauchy–Schwarz and $(g_u+g_v)^2\leq2(g_u^2+g_v^2)$ give
$$ \sum_{uv\in E}\lvert g_u^2-g_v^2\rvert \leq\sqrt{\sum_{uv\in E}(g_u-g_v)^2} \sqrt{2d\sum_vg_v^2}. $$
The ratio is at most $\sqrt{2\mu_2}$, proving the upper inequality and explaining the spectral sweep algorithm.
Solved example. Petersen contains the five-cycle $12,34,15,23,45,12$. Its five vertices each have two neighbors inside and one outside, so its boundary has five edges and its conductance is $5/(3\cdot5)=1/3$. The lower inequality gives $\Phi\geq(2/3)/2=1/3$. Therefore $\Phi=1/3$ and $h=1$, proved without exhaustively searching all cuts. The upper estimate $\sqrt{4/3}$ is loose here and even exceeds one; a valid upper bound need not be informative.
Exercise. Compute the conductance of $C_4$ and compare both bounds. Hint: An adjacent pair has two leaving edges and volume four. Solution: That cut gives $1/2$; singletons give one, so $\Phi=1/2$. Since $\mu_2=1$, the lower bound is sharp and the upper bound $\sqrt2$ is loose. Using the unnormalized Laplacian eigenvalue two in the normalized formula would mix conventions.
31.6 Strongly regular graphs
Optional extension; not required to complete the chapter foundation. Strong regularity replaces arbitrary local common-neighbor counts by two constants. This forces a short matrix identity and usually only three distinct adjacency eigenvalues.
A strongly regular graph with parameters $(v,k,a,c)$ is a nonempty, noncomplete $k$-regular graph on $v$ vertices in which adjacent vertices have $a$ common neighbors and nonadjacent distinct vertices have $c$. The letters $a,c$ avoid confusion with spectral eigenvalues. Counting length-two walks gives
$$ A^2=kI+aA+c(J-I-A)=(k-c)I+(a-c)A+cJ. $$
Double-counting edges from the neighbors of a fixed vertex to its nonneighbors gives the necessary parameter relation
$$ k(k-a-1)=(v-k-1)c. $$
A neighbor has $k-a-1$ neighbors outside that fixed vertex's closed neighborhood; each nonneighbor has $c$ neighbors inside its neighborhood. These counts describe the same edges.
On $\mathbf1^\perp$, the nonprincipal eigenvalues solve
$$ x^2-(a-c)x-(k-c)=0. $$
When the graph is connected, the eigenvalue $k$ is simple, and multiplicities of the two roots are determined by their sum $v-1$ and the trace-zero equation. Parameter feasibility, including integral nonnegative multiplicities, is necessary but does not by itself guarantee existence of a graph.
Solved example. In the Petersen two-subset model, disjoint pairs use four labels, leaving only one: no two-subset can be disjoint from both, so $a=0$. Intersecting distinct pairs use three labels; the remaining two labels give the unique common neighbor, so $c=1$. Its parameters are $(10,3,0,1)$, and $3(3-0-1)=6=(10-3-1)\cdot1$. The equation is $x^2+x-2=0$. If multiplicities of $1,-2$ are $f,g$, then $f+g=9$ and $3+f-2g=0$, giving $f=5,g=4$.
Connectedness follows directly: disjoint pairs are adjacent, and intersecting distinct pairs have a common neighbor. Every pair is therefore at distance at most two. This proves the simple principal eigenvalue hypothesis before using it in the multiplicity calculation.
Exercise. Verify that $C_5$ is strongly regular and compute its nonprincipal eigenvalues. Hint: Adjacent vertices share none; every nonadjacent pair shares one neighbor. Solution: Its parameters are $(5,2,0,1)$, and the roots are $(-1\pm\sqrt5)/2$, each with multiplicity two. Together with eigenvalue two they give trace zero and squared-eigenvalue sum ten, matching its five edges.
31.7 Association schemes and Bose–Mesner algebras
Optional extension; not required to complete the chapter foundation. A graph records one relation between vertices. An association scheme records several relations whose adjacency matrices multiply within a common finite-dimensional algebra.
A symmetric association scheme on a finite set $X$ consists of zero-one symmetric matrices $A_0,\ldots,A_r$ satisfying $A_0=I$, $\sum_iA_i=J$, and
$$ A_iA_j=\sum_{k=0}^r p_{ij}^kA_k. $$
The matrices have disjoint supports; $p_{ij}^k$ counts intermediate vertices $z$ with $(x,z)$ in relation $i$ and $(z,y)$ in relation $j$ whenever $(x,y)$ is in relation $k$. Independence of this count from the chosen pair is the key hypothesis. The span is the Bose–Mesner algebra. Products are symmetric by the closure formula, so $A_iA_j=A_jA_i$; commuting real symmetric matrices admit simultaneous orthogonal diagonalization.
Solved example. Petersen gives a two-class scheme with $A_0=I$, $A_1=A$, $A_2=J-I-A$. Direct substitution yields
$$ A_1^2=3A_0+A_2,\qquad A_1A_2=2A_1+2A_2,\qquad A_2^2=6A_0+4A_1+3A_2. $$
Their simultaneous eigenvalues are
| Common eigenspace | Dimension | $A_0$ eigenvalue | $A_1$ eigenvalue | $A_2$ eigenvalue |
|---|---|---|---|---|
| Constants | $1$ | $1$ | $3$ | $6$ |
| Eigenvalue-one space of $A$ | $5$ | $1$ | $1$ | $-2$ |
| Eigenvalue-minus-two space of $A$ | $4$ | $1$ | $-2$ | $1$ |
For nonconstant vectors, $J$ vanishes, so the last column is $-1$ minus the $A_1$ eigenvalue. The primitive orthogonal projectors are
$$ E_0=J/10,\qquad E_1=(A+2I-5E_0)/3,\qquad E_2=(I-A+2E_0)/3. $$
They satisfy $E_iE_j=\delta_{ij}E_i$, $\sum_iE_i=I$, and have traces $1,5,4$. This gives a second basis of the same algebra: relation matrices describe combinatorial incidences, while projectors describe spectral components. Ordinary matrix multiplication and entrywise multiplication are different operations; do not read the displayed product constants as entrywise identities. For broader background, see Brouwer–Haemers' author-hosted text.
Exercise. Check $A_1A_2=2A_1+2A_2$ on each common eigenspace. Hint: Multiply the two eigenvalues in each row. Solution: The left values are $18,-2,-2$, and the right values are $2(3+6)=18$, $2(1-2)=-2$, and $2(-2+1)=-2$. Since the common eigenspaces span all vectors, these checks prove the matrix identity once simultaneous diagonalization and the table are established.
31.8 Distance-regular graphs
Optional extension; not required to complete the chapter foundation. Distance regularity means that the numbers of neighbors moving closer to, staying equally far from, or moving farther from a base vertex depend only on the current distance.
Let a connected graph have diameter $D$. For vertices $x,y$ at distance $i$, let $c_i,a_i,b_i$ count neighbors of $y$ at distances $i-1,i,i+1$ from $x$. A graph is distance-regular if these numbers depend only on $i$, not on $x,y$. It is then regular of degree $k$, with $c_i+a_i+b_i=k$, $c_0=0$, and $b_D=0$. The intersection array is $\{b_0,\ldots,b_{D-1};c_1,\ldots,c_D\}$.
Let $k_i$ be the number of vertices at distance $i$ from a fixed vertex. Counting edges between consecutive layers gives $k_i b_i=k_{i+1}c_{i+1}$. The distance matrices $A_i$, with entries one on pairs at distance $i$, satisfy
$$ AA_i=b_{i-1}A_{i-1}+a_iA_i+c_{i+1}A_{i+1}, $$
omitting nonexistent terms. Since $c_{i+1}\gt0$ when $i\lt D$, this recurrence expresses each $A_i$ as a polynomial in $A$. The distance relations form a symmetric association scheme. The standard theorem that a connected distance-regular graph has exactly $D+1$ distinct eigenvalues follows from this recurrence and the independent distance matrices; its full algebraic argument is omitted here.
Solved example. Petersen has distance layers of sizes $1,3,6$. Its intersection array is $\{3,2;1,1\}$: a vertex in layer one has one neighbor back, none in its layer, and two forward; a vertex in layer two has one back and two in its own layer. The layer quotient is
$$ Q=\begin{pmatrix}0&3&0\\1&0&2\\0&1&2\end{pmatrix}. $$
Its characteristic polynomial is $(x-3)(x-1)(x+2)$. The quotient yields the distinct eigenvalues, not their multiplicities in the ten-vertex graph. Because $k_i b_i=k_{i+1}c_{i+1}$, conjugation by $\operatorname{diag}(1,\sqrt3,\sqrt6)$ makes the quotient symmetric, with off-diagonal entries $\sqrt3$ and $\sqrt2$. The recurrence gives $A^2=3I+A_2$ and $AA_2=2A+2A_2$, exactly the scheme identities from 31.7.
Exercise. Find the intersection array and spectrum of the cube graph $Q_3$. Hint: Label vertices by binary strings of length three and join strings differing in one coordinate. Solution: At Hamming distance $i$, there are $i$ ways to move back and $3-i$ to move forward, with none in the same layer. The array is $\{3,2,1;1,2,3\}$ and layer sizes are $1,3,3,1$. Functions $(-1)^{a\cdot x}$ are adjacency eigenvectors of eigenvalue $3-2\lvert a\rvert$, yielding $3,1^{[3]},(-1)^{[3]},-3$. This also verifies bipartiteness spectrally.
31.9 Spectral methods for coloring and independence
Optional extension; not required to complete the chapter foundation. An independent set has zero internal adjacency energy. Centering its indicator makes that fact comparable with a least eigenvalue.
Let $G$ be $d$-regular on $n$ vertices with at least one edge, and let $\tau=\lambda_n\lt0$. For an independent set $S$ of size $s\gt0$, put $z=\mathbf1_S-(s/n)\mathbf1$. Then
$$ \lVert z\rVert^2=s-s^2/n,\qquad z^{\mathsf T}Az=-ds^2/n. $$
The second identity follows by expanding, using $A\mathbf1=d\mathbf1$ and $\mathbf1_S^{\mathsf T}A\mathbf1_S=0$. The least-eigenvalue inequality gives
$$ -ds^2/n\geq\tau(s-s^2/n), \qquad \alpha(G)\leq\frac{n(-\tau)}{d-\tau}. $$
Equality forces the centered indicator into the $\tau$ eigenspace. Then a vertex outside $S$ has $-\tau$ neighbors in $S$, while a vertex inside has zero. This follows by substituting the two possible values of $z$ into $Az=\tau z$; it is a useful structural check on an extremal set.
A proper coloring partitions the vertices into independent sets, so $n\leq\chi(G)\alpha(G)$. Consequently the regular-graph Hoffman coloring bound is
$$ \chi(G)\geq1-d/\tau. $$
Round an independence upper bound down and a coloring lower bound up when drawing integer conclusions. These formulas require the stated regularity and negative denominator; the empty graph is handled separately.
Solved example. Petersen has $d=3,\tau=-2$, so $\alpha\leq4$ and $\chi\geq5/2$, hence $\chi\geq3$. The following independent color classes give a proper three-coloring:
$$ \{12,13,14,15\},\qquad \{23,24,25\},\qquad \{34,35,45\}. $$
Within each class labels share a common element or belong to the three pairs on a three-element set, so no two are disjoint. Thus $\chi=3$. The first class attains the independence bound, and every outside vertex has two neighbors in it, as the equality condition predicts.
For $C_5$, the least eigenvalue is $-(1+\sqrt5)/2$. Both the independence upper bound and the unrounded coloring lower bound are $\sqrt5$: after rounding, $\alpha\leq2$ and $\chi\geq3$. Nonadjacent vertices give an independent pair, and an ordinary three-coloring gives equality in the integer conclusions. The real-valued inequalities themselves need not be equalities.
Exercise. Apply the bounds to $K_{3,3}$. Hint: Its spectrum is $3,0^{[4]},-3$. Solution: $\alpha\leq6\cdot3/(3+3)=3$ and $\chi\geq2$. Each side of the bipartition gives an independent triple, and the bipartition is a two-coloring. These sharp conclusions coexist with $\Lambda=d$: good independence bounds do not automatically mean two-sided pseudorandomness.
31.10 Spectral pseudorandomness
Optional extension; not required to complete the chapter foundation. A deterministic graph can distribute edges approximately like a uniform density model. The quantitative meaning here is discrepancy between vertex sets, not independent random choices of edges.
For a regular graph set $\Lambda=\max_{i\geq2}\lvert\lambda_i\rvert$, retaining all nonprincipal eigenvalues even if $d$ repeats. Define the ordered edge count
$$ e(S,T)=\mathbf1_S^{\mathsf T}A\mathbf1_T. $$
For disjoint sets this counts each crossing edge once. For $S=T$ it counts internal edges twice. For overlapping sets the matrix definition removes ambiguity. The expander mixing lemma states the refined bound
$$ \left\lvert e(S,T)-\frac{d\lvert S\rvert\lvert T\rvert}{n}\right\rvert \leq\Lambda\sqrt{\lvert S\rvert(1-\lvert S\rvert/n)\lvert T\rvert(1-\lvert T\rvert/n)} \leq\Lambda\sqrt{\lvert S\rvert\lvert T\rvert}. $$
Proof. Center the indicators as $x=\mathbf1_S-(\lvert S\rvert/n)\mathbf1$ and $y=\mathbf1_T-(\lvert T\rvert/n)\mathbf1$. The discrepancy equals $x^{\mathsf T}Ay$. On $\mathbf1^\perp$, the operator norm of $A$ is $\Lambda$, so its absolute value is at most $\Lambda\lVert x\rVert\lVert y\rVert$. Computing the two squared norms gives the refined expression. This is a proof for all sets simultaneously, not a random-sampling argument.
The expected density term is $d/n$, arising from the rank-one matrix $(d/n)J$. It includes diagonal entries even though the actual simple graph has no loops; the discrepancy term accounts for that. It is therefore not exactly the marginal edge probability $d/(n-1)$ in a uniform random regular graph. Strong relative guarantees require the density term to dominate the error; small sets may receive a loose bound even when $\Lambda/d$ is small.
Solved example. In Petersen, take $S=\{12,13,14,15\}$ and $T=V\setminus S$. Then $\lvert S\rvert=4$, $\lvert T\rvert=6$, and $e(S,T)=12$. The density term is $3\cdot4\cdot6/10=36/5$, so the discrepancy is $24/5$. The refined upper bound is
$$ 2\sqrt{4(1-4/10)\cdot6(1-6/10)}=24/5. $$
It is exact. With $S=T$ equal to the independent four-set, the actual ordered count is zero, the density term is $24/5$, and the same refined error again gives equality. The centered indicator lies in the minus-two eigenspace, explaining the saturation. Petersen is a small illustration; its ratio $\Lambda/d=2/3$ is not an asymptotically vanishing pseudorandomness parameter.
The matrix viewpoint connects the chapter: $A=(d/n)J+R$ with $\lVert R\rVert_{\mathrm{op}}=\Lambda$; regularity also gives $L=dI-A=BB^{\mathsf T}$. Thus incidence energy controls cut variation, while the same adjacency eigenspaces control discrepancy. One-sided gap bounds and absolute discrepancy bounds use different portions of that spectrum.
Exercise. Find $\Lambda/d$ for $K_n$ and explain what its small value means. Hint: $A=J-I$. Solution: The nonprincipal eigenvalues are all minus one, so $\Lambda/d=1/(n-1)\to0$. This deterministic dense family has uniformly small spectral discrepancy relative to its degree. It demonstrates that pseudorandom edge distribution does not require the graph itself to have been sampled randomly.
Compute a spectrum and compare spectral bounds with exact graph parameters
The investigation compares a certified spectrum with exact independence, coloring, and cut data. Its foundation track uses the opening definitions and stated tools; algebraic schemes and further spectral theory are optional extensions. Keep every reported eigenvalue attached to its matrix and every bound attached to its hypotheses.
Compute a spectrum and compare spectral bounds with exact graph parameters
Input graph. Use the ordered vertices $12,13,14,15,23,24,25,34,35,45$, with adjacency exactly when labels are disjoint. Use a signed incidence matrix with one column per unordered edge, oriented from the earlier vertex to the later one. This specifies the graph without relying on the drawing.
Deliverables and rubric, 100 points.
| Task | Required evidence | Points |
|---|---|---|
| Warm-up | Adjacency, degrees, fifteen edges, incidence orientation, and $BB^{\mathsf T}=3I-A$ | 20 |
| Spectrum proof | Common-neighbor identity, connectedness, and exact eigenvalue multiplicities | 25 |
| Bound comparison | Independence and coloring certificates; cut witness and conductance bound | 25 |
| Finite exploration | Exhaustive set data or exact computational procedure, plus mixing discrepancy | 20 |
| Interpretation | Validation limits, matrix conventions, and one application | 10 |
1. Warm-up. Construct $A,B,L,\mathcal L$ and check symmetry, zero adjacency diagonal, degree three, and all matrix sizes. Hint: $A$ is $10\times10$, $B$ is $10\times15$, $L=3I-A$, and $\mathcal L=L/3$.
2. Proof problem. Prove $A^2=2I-A+J$, then derive the exact spectrum. Hints: Distinguish equal, adjacent, and nonadjacent vertex pairs. Prove connectedness from their common-neighbor descriptions. Use $\operatorname{tr}A=0$ to determine multiplicities, not only the quadratic roots.
3. Bounds and witnesses. Use the least eigenvalue to bound $\alpha$ and $\chi$, and supply a maximum independent set and proper coloring. Use the five-cycle $12,34,15,23,45,12$ as a conductance witness and compare it with the Cheeger lower bound. Hint: Its boundary consists of five edges. A witness proves one inequality direction; the spectral bound supplies the opposite direction.
4. Computational or visual exploration. Enumerate all $2^{10}=1024$ vertex subsets. Test independence by counting internal edges; for each size $s=1,\ldots,5$, record the minimum boundary size. Independently compare $e(S,V\setminus S)$ with the refined mixing bound for the independent four-set. If using numerical eigenvalues, also report eigenvector residual norms, trace and squared-trace checks, and the exact algebraic spectrum from task 2. Floating-point output alone is insufficient to certify a rounded integer inequality.
Optional open-ended extension, ungraded. Repeat the study for $C_5$, $K_{3,3}$, and $Q_3$. Compare sharpness of independence bounds and one-sided gaps with their absolute parameters. Explain which ordinary walks are periodic and how laziness changes the spectrum. Alternatively reconstruct the three Bose–Mesner projectors of Petersen and verify their multiplication and traces exactly. These are explorations of established results, not assertions about the status of an open problem.
Validation method. Use exact integer adjacency and edge counts. Verify the common-neighbor identity entry by entry and the multiplicities algebraically. Exhaustive subsets certify the reported finite maxima and minima when every subset is included. A proper coloring certifies an upper bound on $\chi$; the spectral inequality certifies its lower bound. General Cheeger and mixing proofs support all-set conclusions, whereas testing selected cuts or set pairs checks only those instances.
Worked solutions. Each two-subset is disjoint from $\binom32=3$ other two-subsets, so the graph is cubic and has $10\cdot3/2=15$ edges. The signed incidence product is $L=3I-A$, independent of the chosen orientation. The common-neighbor proof in 31.6 establishes the matrix identity exactly. Connectedness and the trace equation then give
| Matrix | Exact spectrum, with multiplicities |
|---|---|
| $A$ | $3^{[1]},1^{[5]},(-2)^{[4]}$ |
| $L$ | $0^{[1]},2^{[5]},5^{[4]}$ |
| $\mathcal L$ | $0^{[1]},(2/3)^{[5]},(5/3)^{[4]}$ |
Thus $\mu_2=2/3$, $\tau=-2$, and $\Lambda=2$. The characteristic polynomial of $A$ is $(x-3)(x-1)^5(x+2)^4$. Its trace is zero, its squared-eigenvalue sum is thirty, and the Laplacian trace is thirty. These are useful independent checks, though moment checks alone would not uniquely certify the whole spectrum.
Hoffman's bound and the four labels containing one prove $\alpha=4$. The rounded coloring lower bound is three, and the three classes in 31.9 give $\chi=3$. The boundary profile from exhaustive enumeration is
| Subset size $s$ | Minimum $\lvert\partial S\rvert$ | Minimum ratio $\lvert\partial S\rvert/(3s)$ at that size |
|---|---|---|
| $1$ | $3$ | $1$ |
| $2$ | $4$ | $2/3$ |
| $3$ | $5$ | $5/9$ |
| $4$ | $6$ | $1/2$ |
| $5$ | $5$ | $1/3$ |
The minimum conductance is $1/3$, in agreement with the five-cycle witness and the matching spectral lower bound. To explain the profile without treating software output as an unexplained oracle, note that Petersen has no triangles or four-cycles. A four-cycle would give two common neighbors to a nonadjacent pair, contradicting $c=1$. For subsets of sizes at most four, the induced graph is therefore a forest and has at most $s-1$ edges. These maxima are attained by an edge, a three-vertex path, and a four-vertex path. On five vertices, an induced cycle can only have length five; a chord would create a triangle or four-cycle. Thus at most five internal edges occur, attained by the displayed cycle. The identity $\lvert\partial S\rvert=3s-2\lvert E(S)\rvert$ gives every entry.
There are five maximum independent sets: all two-subsets containing a fixed label, one choice for each of the five labels. Exhaustive enumeration checks that no others occur. The matrix certificate already rules out larger sets; proving this complete classification by a separate intersecting-family argument is optional. The independent-set/complement ordered edge count is twelve, with discrepancy $24/5$ and refined error $24/5$, as calculated in 31.10. Supply both the count and the centered norms to receive full comparison credit.
The extension comparisons include $\alpha(C_5)=2,\chi(C_5)=3$; $\alpha(K_{3,3})=3,\chi(K_{3,3})=2$; and $\alpha(Q_3)=4,\chi(Q_3)=2$. The last two have eigenvalue minus their degree, so their nonlazy walks are periodic despite positive one-sided gaps. Their spectra should be verified by the constructions in the relevant sections rather than guessed from a drawing.
A cross-disciplinary application is spectral partitioning of a network. The incidence energy $\lVert B^{\mathsf T}f\rVert^2$ measures disagreement across edges; a low normalized eigenvalue can identify a bottleneck, and sweeping its eigenvector coordinates produces candidate cuts with the guarantee proved in 31.5. Meanwhile a small absolute nonprincipal adjacency norm bounds deviations from uniform edge distribution. These certificates help distinguish a separable network from one with broadly distributed connections. For Petersen, the balanced five-cycle cut is already an exact eigenvector witness: its centered indicator has adjacency eigenvalue one and Laplacian eigenvalue two. A certified spectrum supplies the bound, and the explicit cut supplies its combinatorial interpretation.
Next in the Series
In Chapter 32: Matroid Theory, we'll explore A common language for independence, greedy choice, and duality.