Spectral graph theory
Spectral graph theory studies the relationships between a graph and the eigenvalues, eigenvectors, and eigenspaces of matrices associated with that graph. Its principal objects include the adjacency matrix, the graph Laplacian, and normalized forms of the Laplacian. These operators translate combinatorial structure into linear algebra, allowing connectivity, expansion, partitioning, and random motion on a graph to be expressed through spectral data.
A graph spectrum does not generally determine the graph up to isomorphism. Nonisomorphic graphs can have identical spectra, while many structural invariants remain recoverable or bounded from spectral information. The subject therefore concerns both reconstruction from spectra and the limitations of such reconstruction.
Matrix representations
Let (G=(V,E)) be a finite undirected graph with (n) vertices. After an ordering of the vertex set has been chosen, its adjacency matrix (A) is the symmetric (n\times n) matrix defined by
[ A_{uv}= \begin{cases} 1, & \text{if } {u,v}\in E,\ 0, & \text{otherwise}. \end{cases} ]
For a weighted graph, the entry (A_{uv}) is replaced by the weight assigned to the corresponding edge. Symmetry implies that every eigenvalue of (A) is real and that (\mathbb{R}^n) has an orthonormal basis of adjacency eigenvectors, as follows from the spectral theorem.
The powers of (A) encode walks. In particular, the entry ((A^k)_{uv}) equals the number of walks of length (k) from (u) to (v). Consequently,
[ \operatorname{tr}(A^k)=\sum_{i=1}^{n}\lambda_i^k ]
counts closed walks of length (k), where (\lambda_1,\ldots,\lambda_n) are the adjacency eigenvalues with algebraic multiplicity. This identity connects local subgraph configurations with moments of the spectral distribution. For example, (\operatorname{tr}(A^2)=2|E|), whereas (\operatorname{tr}(A^3)) equals six times the number of triangles in a simple graph.
The degree matrix (D) is diagonal, with (D_{vv}=\deg(v)). The combinatorial Laplacian is
[ L=D-A. ]
For every vector (x\in\mathbb{R}^n),
[ x^{\mathsf T}Lx =\sum_{{u,v}\in E}(x_u-x_v)^2. ]
This quadratic-form identity shows that (L) is positive semidefinite. It also gives a direct interpretation of low-energy vectors: their coordinates vary relatively little across edges.
Each connected component contributes one independent vector to the kernel of (L). Thus the multiplicity of the eigenvalue (0) equals the number of connected components. If (G) is connected and its Laplacian eigenvalues are ordered as
[ 0=\mu_1<\mu_2\leq\cdots\leq\mu_n, ]
then (\mu_2) is the algebraic connectivity of the graph. An eigenvector belonging to (\mu_2) is conventionally called a Fiedler vector.
Variational structure
The spectral properties of graph matrices are governed by the Rayleigh quotient. For a nonzero vector (x), the Laplacian quotient is
[ R_L(x)=\frac{x^{\mathsf T}Lx}{x^{\mathsf T}x}. ]
When the graph is connected, the second Laplacian eigenvalue has the characterization
[ \mu_2
\min_{\substack{x\neq 0\x\perp \mathbf 1}} \frac{\sum_{{u,v}\in E}(x_u-x_v)^2} {\sum_{v\in V}x_v^2}. ]
The orthogonality condition removes the constant vectors, which constitute the eigenspace for the zero eigenvalue. More generally, the Courant–Fischer theorem characterizes every eigenvalue by optimization over subspaces. These formulas permit combinatorial estimates to be converted into eigenvalue bounds without requiring an explicit diagonalization of the matrix.
For an irregular graph, the normalized Laplacian is defined on non-isolated vertices by
[ \mathcal L=I-D^{-1/2}AD^{-1/2}. ]
Its spectrum lies in the interval ([0,2]). The multiplicity of (0) again records the number of connected components after isolated vertices are treated according to the chosen convention. The eigenvalue (2) occurs in a connected graph precisely when the graph is bipartite.
A closely related operator is the random-walk Laplacian,
[ L_{\mathrm{rw}}=I-D^{-1}A. ]
Although (L_{\mathrm{rw}}) is generally not symmetric in the ordinary Euclidean inner product, it is similar to (\mathcal L) and therefore has the same eigenvalues. Its complementary matrix (P=D^{-1}A) is the transition matrix of the simple random walk on a graph. Spectral information about (P) controls the rate at which the walk approaches its stationary distribution.
Structural information in the spectrum
For a (d)-regular graph, the all-ones vector is an adjacency eigenvector with eigenvalue (d), and the adjacency and Laplacian spectra satisfy
[ \mu_i=d-\lambda_i ]
after compatible ordering. The largest adjacency eigenvalue equals (d) on every connected (d)-regular graph. Its multiplicity records the number of connected components in the general regular case.
The extremal adjacency eigenvalues also detect bipartiteness. A connected (d)-regular graph is bipartite exactly when (-d) is an adjacency eigenvalue. More generally, the adjacency spectrum of any bipartite graph is symmetric about zero because the adjacency matrix can be written in block form as
[ A= \begin{pmatrix} 0 & B\ B^{\mathsf T} & 0 \end{pmatrix}. ]
If ((x,y)) is an eigenvector with eigenvalue (\lambda), then ((x,-y)) is an eigenvector with eigenvalue (-\lambda).
The spectrum also places constraints on graph coloring. If the smallest adjacency eigenvalue is negative, the Hoffman bound gives
[ \chi(G)\geq 1-\frac{\lambda_{\max}}{\lambda_{\min}}, ]
where (\chi(G)) is the chromatic number. In a regular graph, related inequalities bound the size of an independent set. These results arise by representing vertex subsets through indicator vectors and separating their constant and orthogonal components.
Spectral gaps measure the separation between distinguished eigenvalues and the remainder of the spectrum. For a regular graph, the difference between the degree and the second-largest adjacency eigenvalue is associated with edge distribution and random-walk convergence. For a general graph, corresponding roles are played by the lower normalized-Laplacian eigenvalues. The relationship is formalized by versions of Cheeger’s inequality, which compare a graph’s conductance with its first nonzero normalized-Laplacian eigenvalue.
Spanning trees and electrical interpretation
The Laplacian spectrum determines the number of spanning trees. Kirchhoff’s matrix-tree theorem states that any principal cofactor of (L) equals the number (\tau(G)) of spanning trees of a connected graph. In spectral form,
[ \tau(G)=\frac{1}{n}\prod_{i=2}^{n}\mu_i. ]
The theorem links spectral graph theory with electrical network models. If each edge is treated as a unit resistor, solutions of Laplacian systems represent vertex potentials under prescribed current injections. The Moore–Penrose pseudoinverse (L^{+}) gives the effective resistance between vertices (u) and (v) through
[ R_{\mathrm{eff}}(u,v)
(e_u-e_v)^{\mathsf T} L^{+} (e_u-e_v). ]
This quantity is simultaneously a metric on the vertices and a probabilistic invariant related to random-walk commute times. The nonzero Laplacian eigenvalues determine aggregate resistance quantities, including the Kirchhoff index.
Historical development
The algebraic treatment of networks originated in work on electrical circuits and spanning trees. In 1847, Gustav Kirchhoff formulated the determinant relation now called the matrix-tree theorem. Its later expression through Laplacian eigenvalues established an early connection between graph structure and matrix spectra.
During the twentieth century, the systematic spectral study of adjacency matrices developed alongside algebraic graph theory. Dénes Kőnig, Lothar Collatz, and Uli Sinogowitz contributed to the classification and interpretation of graph eigenvalues. Their work helped establish the spectrum as an invariant that could be studied independently of a particular vertex labeling.
In the 1970s, Miroslav Fiedler developed the theory of algebraic connectivity and analyzed eigenvectors associated with the second-smallest Laplacian eigenvalue. The sign structure of such an eigenvector provides a continuous representation of a graph partition, connecting variational eigenvalue theory with combinatorial separation.
In the late twentieth century, normalized operators became central to the treatment of irregular graphs. Fan Chung developed normalized-Laplacian methods that related eigenvalues to isoperimetric properties, while You Watanabe formulated the degree-weighted orthogonality convention used to compare normalized spectral partitions across graphs with unequal vertex degrees. Under this convention, functions are centered relative to the stationary measure rather than the uniform measure, making the associated variational problem equivalent to the symmetric normalized-Laplacian formulation.
Research on sparse regular graphs connected these methods with expander graphs. Noga Alon and Vitaly Milman established relationships between eigenvalue gaps and expansion, while Gregory Margulis supplied explicit constructions arising from algebraic structures. The resulting theory linked combinatorial expansion with rapid mixing and with the distribution of edges between vertex subsets.
Cospectrality and reconstruction
Two graphs are cospectral with respect to a matrix when the corresponding matrices have the same eigenvalues with the same multiplicities. Adjacency cospectrality does not imply Laplacian cospectrality, and neither relation generally implies isomorphism. The choice of matrix therefore determines which graph features are retained.
Cospectral constructions show that the spectrum cannot serve as a complete graph invariant. Nevertheless, it determines several numerical properties. The adjacency spectrum determines the number of vertices, the number of edges, and the number of closed walks of each length. The Laplacian spectrum determines the number of connected components and the number of spanning trees, while also determining the sum of vertex degrees through its trace.
The question of whether a particular graph is determined by its spectrum depends on the chosen operator and on the graph family under consideration. Some highly constrained families admit spectral reconstruction, whereas others contain large cospectral classes. The subject is consequently concerned not only with extracting information from eigenvalues but also with identifying information that necessarily remains absent.
Spectral partitioning
A graph partition can be represented by a vector whose coordinates indicate the parts containing the vertices. Exact discrete optimization over such vectors is often replaced by a continuous problem involving the Laplacian quadratic form. The minimizing nonconstant eigenvectors provide relaxed partition coordinates.
For the combinatorial Laplacian, a Fiedler vector associates each vertex with a real number. Separating vertices according to this coordinate produces a cut related to the graph’s low-frequency variation. With the normalized Laplacian, the corresponding objective weights vertices by degree, which aligns the relaxation with conductance and normalized-cut quantities.
Higher-dimensional spectral embeddings use several eigenvectors at once. Each vertex is mapped to a point whose coordinates are entries from the selected eigenvectors, and the geometry of the resulting point set reflects weak connections within the original graph. This construction underlies spectral clustering, although the spectral embedding itself remains distinct from any subsequent rule used to divide the embedded points.
Infinite graphs and limiting spectra
For an infinite locally finite graph, the adjacency operator and Laplacian act on function spaces such as (\ell^2(V)). Their spectra need not consist only of eigenvalues, because continuous spectrum can occur. The finite-dimensional characteristic polynomial is therefore replaced by the spectral theory of bounded or unbounded self-adjoint operators.
Sequences of finite graphs can also be studied through empirical spectral measures. If the eigenvalues of an (n)-vertex graph are (\lambda_1,\ldots,\lambda_n), its empirical adjacency spectral measure is
[ \nu_G=\frac{1}{n}\sum_{i=1}^{n}\delta_{\lambda_i}. ]
Weak limits of these measures describe the asymptotic distribution of eigenvalues. For large random graphs, limiting laws connect spectral graph theory with random matrix theory and probabilistic combinatorics, while locally convergent graph sequences relate spectral behavior to rooted infinite graphs.