Introduction to Spectral Graph Theory

Spectral graph theory is not a museum piece; it is load-bearing infrastructure across several fields.

Spectral clustering and partitioning. The eigenvector associated with $\lambda_2$ (the Fiedler vector) is used to split a graph into two well-connected pieces with a small cut — the basis of spectral clustering algorithms in machine learning and image segmentation, where a similarity graph is built on data points and its Laplacian's low eigenvectors reveal cluster structure.

Expander graphs and pseudorandomness. A family of graphs is a good expander precisely when the gap between the top two adjacency eigenvalues (or, equivalently, $\lambda_2$ of the Laplacian relative to the maximum degree) stays bounded away from zero; expanders underlie error-correcting codes, derandomization, and network design in theoretical computer science.

Random walks and Markov chains. The normalized Laplacian's eigenvalues govern the mixing time of a random walk on a graph — how quickly the walk's distribution converges to uniform — which matters for Monte Carlo sampling algorithms and for analyzing web-scale random surfer models such as PageRank.

Chemistry and physics. Hückel molecular orbital theory computes bonding/antibonding energy levels of conjugated hydrocarbons as eigenvalues of the molecule's adjacency matrix, an early and direct physical application predating much of the graph-theoretic formalization.

Cryptography and coding theory. Strongly regular graphs and their prescribed eigenvalue structure underlie constructions of optimal error-correcting codes and combinatorial designs, connecting spectral graph theory to algebraic coding theory.

Network science and robustness. Algebraic connectivity is used as a quantitative robustness measure for communication and power networks: a larger $\lambda_2$ signals that more edges must be removed to disconnect the network, informing infrastructure design against targeted or random failures.

Ask the tutor: How does the algebraic connectivity $\lambda_2$ relate quantitatively to the edge-connectivity and vertex-connectivity of a graph?

Think of the adjacency matrix $A$ as an operator that moves mass along edges: if $x \in \mathbb{R}^n$ assigns a value $x_i$ to vertex $v_i$, then $(Ax)_i = \sum_{j \sim i} x_j$ is the sum of $x$ over the neighbors of $v_i$. Iterating $A$ counts walks: the entry $(A^k)_{ij}$ equals the number of walks of length $k$ from $v_i$ to $v_j$. This is why the adjacency spectrum controls global counting statistics such as the number of closed walks (the trace of $A^k$) and, via the Matrix-Tree Theorem and companion identities, other enumerative invariants. The Laplacian has a complementary, more geometric role: it measures disagreement across edges. For $x \in \mathbb{R}^n$,

a sum of squared differences across every edge (we prove this identity below). This quadratic form is visibly $\ge 0$, and it is $0$ exactly when $x$ is constant on each connected component — capturing connectivity as an algebraic condition. This is the reason $\lambda_2$, the smallest nonzero possible Laplacian eigenvalue, serves as a connectivity gauge: making $\lambda_2$ small means you can find a nonconstant $x$ that changes very little across most edges, i.e., the graph can be almost split into two loosely connected pieces (a small "cut").

Example 1: the "paw" graph (asymmetric, non-regular). Let $G$ have vertex set $\{1,2,3,4\}$ and edges $\{12, 13, 23, 34\}$ — a triangle on $\{1,2,3\}$ with a pendant edge to $4$ attached at vertex $3$. This graph is deliberately irregular (degrees $2,2,3,1$) and not bipartite, to avoid any hidden symmetry. Adjacency matrix.

Its characteristic polynomial is computed by expanding $\det(A - tI)$:

Expanding along the last row: entries are $0,0,1,-t$, so

with appropriate cofactor signs. Concretely, expand along row 4: the term for column 3 (entry $1$) has cofactor sign $(-1)^{4+3}=-1$, and its minor is $\det\begin{pmatrix}-t&1&0\\1&-t&0\\1&1&1\end{pmatrix}$. Expanding this minor along its last column gives $1\cdot\det\begin{pmatrix}-t&1\\1&-t\end{pmatrix} = t^2-1$. So this term contributes $1\cdot(-1)\cdot(t^2-1) = -(t^2-1) = 1-t^2$. The term for column 4 (entry $-t$) has cofactor sign $(-1)^{4+4}=+1$, and its minor is $\det\begin{pmatrix}-t&1&1\\1&-t&1\\1&1&-t\end{pmatrix}$. This is the characteristic polynomial (in $-t$-style) of the triangle $K_3$'s adjacency structure; direct expansion:

So this term contributes $(-t)(-t^3+3t+2) = t^4 - 3t^2-2t$. Adding both contributions:

So the characteristic polynomial is $p(t) = t^4 - 4t^2 - 2t + 1$. As a check, the sum of eigenvalues equals $\operatorname{tr}(A) = 0$, consistent with the coefficient of $t^3$ being $0$. Also $\det(A) = p(0)$'s constant term relation: $\det(A - 0\cdot I)= \det A$, and indeed $\det A = 1$ matches the constant term $1$ of $p(t)$ up to sign convention $p(t) = \det(A-tI)$, $p(0)=\det A = 1$; direct computation of $\det A$ (expanding row 4: only entry $A_{43}=1$ contributes, cofactor $(-1)^{4+3}\det\begin{pmatrix}0&1&0\\1&0&0\\1&1&1\end{pmatrix}$; that $3\times 3$ determinant expands to $0\cdot(0-0)-1\cdot(1-0)+0 = -1$, so contribution is $1\cdot(-1)\cdot(-1) = 1$) gives $\det A = 1$. Matches. Numerically solving $t^4-4t^2-2t+1=0$ gives four real roots approximately

(sum $\approx 0$, consistent with trace $0$; not symmetric about $0$, consistent with $G$ not bipartite, since it contains the triangle $123$). Laplacian matrix. Degrees are $\deg(1)=2,\deg(2)=2,\deg(3)=3,\deg(4)=1$, so

We know $\lambda_1 = 0$ with eigenvector $\mathbf 1=(1,1,1,1)^\top$ (check: row 1 gives $2-1-1+0=0$; row 3 gives $-1-1+3-1=0$; row 4 gives $0+0-1+1=0$ — confirmed). Since $G$ is connected (visibly: $4$–$3$–$1$–$2$ all reachable), Theorem [Basic spectral facts about the Laplacian] guarantees $\lambda_2>0$. The characteristic polynomial of $L$ is $\det(L-tI)$; using $\operatorname{tr}(L)=2+2+3+1=8=\sum \lambda_i$ and known $\lambda_1=0$, plus the Matrix-Tree relation below, we can get the remaining eigenvalues without full expansion. By the Matrix-Tree Theorem, the number of spanning trees $\tau(G)$ equals any cofactor of $L$, and also equals

Direct combinatorial count of spanning trees of the paw graph: we need spanning trees of a $4$-vertex graph with $4$ edges $\{12,13,23,34\}$; a spanning tree has $3$ edges, and removing any one edge from a graph with exactly one cycle (the triangle $123$) and one bridge ($34$) gives a spanning tree iff we don't disconnect it: the bridge $34$ must always be kept (removing it disconnects vertex $4$), and we must remove exactly one edge of the triangle $\{12,13,23\}$ to kill the cycle while keeping connectivity — all $3$ choices work. So $\tau(G) = 3$. Then $\lambda_2\lambda_3\lambda_4 = n\tau(G) = 4\cdot 3=12$, and $\lambda_2+\lambda_3+\lambda_4 = \operatorname{tr}(L) - \lambda_1 = 8$. Numerically solving the cubic factor of $\det(L-tI)/(-t)$ (degree-3 factor with sum $8$, and product $12$) alongside the sum of pairwise products (which equals the coefficient data from $\det(L - tI)$'s $t^1$ coefficient) gives approximately

(product $\approx 1.198\times 3.000\times 3.802 \approx 13.67$ — to present a fully honest computation we instead solve numerically: the characteristic polynomial of $L$ is $t^4 - 8t^3+21t^2-16t = t(t^3-8t^2+21t-16)$; factoring out the known root $t=1$ of the cubic — check $1-8+21-16=-2\ne 0$, so $t=1$ is not a root; instead solve $t^3-8t^2+21t-16=0$ numerically, giving roots approximately $t\approx 1.271,\ 3.000,\ 3.729$, with product $1.271\times3\times3.729\approx 14.22$). Given the arithmetic subtlety, we verify $\tau(G)=3$ directly is trustworthy (elementary counting above), and we report the Laplacian spectrum as

rounded to three decimals (these satisfy sum $=8.000$ and product of nonzero ones $1.268\times3.000\times3.732\approx 14.20$, and $n\tau(G) = 12$; the small residual discrepancy is rounding — exact roots of $t^3-8t^2+21t-16$ are irrational and the exact product of all three roots is $16$ by Vieta, not $12$; since $\lambda_2\lambda_3\lambda_4$ should equal $n\tau(G)=12$ by Matrix-Tree, and Vieta's product of the cubic's roots is $16$, this signals we must double check $\tau(G)$: reconsider — the paw graph actually has spanning trees counted as follows: total spanning trees of a graph with one triangle and one pendant edge is (number of spanning trees of triangle, which is $3$) times (forced inclusion of bridge, $1$ way) $=3$; Vieta says product of roots of $t^3-8t^2+21t-16$ is $16$ (constant term with sign $(-1)^3\cdot(-16)=16$), and Matrix–Tree states $n\tau(G)=\lambda_2\lambda_3\lambda_4=16$ hence $\tau(G) = 16/4=4$. Re-examining the combinatorics: a spanning tree needs $3$ edges out of the $4$ present; removing one edge from $\{12,13,23\}$ each gives a spanning tree ($3$ trees), and removing the edge $34$ disconnects vertex $4$, giving $0$ additional trees — so indeed $\tau(G)=3$, not $4$. This exposes an arithmetic error in deriving the characteristic polynomial of $L$ above, not in the combinatorics.) Rather than let a shaky quartic expansion stand, we settle this example by trusting the two independently reliable facts — $\tau(G) = 3$ by direct, elementary enumeration, and $\operatorname{tr}(L) = 8$ by direct entrywise summation of degrees — and we present the Laplacian spectrum via consistency: $\lambda_1=0$, $\lambda_2+\lambda_3+\lambda_4=8$, $\lambda_2\lambda_3\lambda_4 = n\tau(G) = 4\cdot3=12$. Solving numerically the correctly-normalized cubic $t^3 - 8t^2 + c_1 t - 12=0$ for the true middle coefficient $c_1$ (obtainable as the sum of $2\times2$ principal-minor-type Laplacian data, namely $c_1=\sum \lambda_i\lambda_j$ over unordered pairs $i<j$ among $\{2,3,4\}$, which equals half of $\big((\sum\lambda_i)^2-\sum\lambda_i^2\big)$ restricted to nonzero eigenvalues) requires $\sum_{i\ge2}\lambda_i^2 = \operatorname{tr}(L^2) - 0^2$. Computing $\operatorname{tr}(L^2)=\sum_{i,j}L_{ij}^2$ directly from the matrix: rows contribute $(4+1+1+0)+(1+4+1+0)+(1+1+9+1)+(0+0+1+1) = 6+6+12+2=26$. So $\sum_{i\ge2}\lambda_i^2 = 26$, and $c_1 = \tfrac{1}{2}\big(8^2-26\big)=\tfrac{1}{2}(64-26)=19$. So the genuine cubic is $t^3-8t^2+19t-12=0$, which factors as $(t-1)(t-3)(t-4)$ — checking: $(t-1)(t-3)=t^2-4t+3$, times $(t-4)$: $t^3-4t^2+3t-4t^2+16t-12=t^3-8t^2+19t-12$. ✓. Roots $1,3,4$, product $12=n\tau(G)$ ✓, sum $8$ ✓. So the corrected, verified Laplacian spectrum of the paw graph is

This matches $\tau(G) = \tfrac14(1\cdot3\cdot4) = 3$, agreeing with the direct count. (Lesson embedded in this example: always cross-check a spectral computation against an independent combinatorial invariant such as $\tau(G)$ or $\operatorname{tr}(L)$.)

Example 2: a graph on $5$ vertices with a cut vertex (checking $\lambda_2$ and disconnection sensitivity). Let $H$ be the "bull-minus" graph: vertices $\{1,2,3,4,5\}$, edges $\{12,13,23,34,45\}$ — again a triangle $123$ with a path $3$–$4$–$5$ hanging off it. Degrees: $\deg1=2,\deg2=2,\deg3=3,\deg4=2,\deg5=1$.

$H$ is connected (it's a tree plus one extra edge closing the triangle), so by the theorem $\lambda_2 > 0$ is guaranteed without further computation — this alone certifies connectivity spectrally. To also illustrate the sensitivity of $\lambda_2$, consider deleting edge $34$ (the bridge connecting the triangle to the tail): the resulting graph $H'$ has two components, $\{1,2,3\}$ (a triangle) and $\{4,5\}$ (an edge), so by Part 4 of the theorem the multiplicity of eigenvalue $0$ jumps from $1$ to $2$, i.e. $\lambda_2(H') = 0$ exactly. This shows explicitly how removing the single bridge edge collapses $\lambda_2$ from a strictly positive value to zero — the qualitative content of algebraic connectivity as a "how many bridges stand between you and disconnection" gauge. We compute $\tau(H)$ directly: the only cycle in $H$ is the triangle $123$; edges $34,45$ are bridges and must be kept in every spanning tree. As in Example 1, we get to choose which of the $3$ triangle edges to delete, giving $\tau(H) = 3$. By Matrix-Tree, $\lambda_2\lambda_3\lambda_4\lambda_5 = n\,\tau(H) = 5\cdot 3=15$, and $\sum_{i=2}^5\lambda_i = \operatorname{tr}(L) = 2+2+3+2+1=10$.