A graph does not look like a matrix, yet every finite graph can be turned into one, and the eigenvalues of that matrix encode a surprising amount of the graph's combinatorial structure: how connected it is, whether it is bipartite, how many colors its vertices need, and even how densely it can possibly be built in the first place. This bridges graph theory with the theory of eigenvalues and eigenvectors.
Graphs as Matrices
Let \(G=(V,E)\) be a finite, undirected, simple graph (no loops, no multiple edges) with vertex set \(V=\{1,\ldots,n\}\). Its adjacency matrix \(\mathbf{A}\in\{0,1\}^{n\times n}\) is defined by
\[a_{ij}=\begin{cases}1 & \text{if } \{i,j\}\in E\\0 & \text{otherwise.}\end{cases}\]
Since edges are unordered, \(\mathbf{A}\) is symmetric, so all of its eigenvalues are real and it has an orthonormal eigenbasis. The degree of vertex \(i\) is \(d_i=\sum_j a_{ij}\), the number of edges incident to it; \(G\) is called \(d\)-regular if \(d_i=d\) for every vertex.
Powers of \(\mathbf{A}\) count walks: entry \((\mathbf{A}^k)_{ij}\) is the number of walks of length \(k\) from \(i\) to \(j\) (sequences of \(k\) edges, with vertices possibly repeated). This follows directly from the definition of matrix multiplication,
\[(\mathbf{A}^2)_{ij}=\sum_{k}a_{ik}a_{kj},\]
which counts exactly the vertices \(k\) adjacent to both \(i\) and \(j\), i.e. the two-step walks between them; the same argument extended by induction gives \((\mathbf{A}^k)_{ij}=\sum_l a_{il}(\mathbf{A}^{k-1})_{lj}\), one more step appended to every walk of length \(k-1\).
The Largest Eigenvalue: Degree Bounds and the Perron–Frobenius Theorem
If \(G\) is \(d\)-regular, the all-ones vector \(\mathbf{e}=(1,\ldots,1)^T\) satisfies \(\mathbf{Ae}=d\mathbf{e}\) (the \(i\)-th entry of \(\mathbf{Ae}\) is the sum of row \(i\), which is \(d_i=d\)): \(\mathbf{e}\) is an eigenvector with eigenvalue \(d\), and, as follows below, this is in fact the largest eigenvalue of \(\mathbf{A}\). For a general, not necessarily regular graph, the same idea via the Rayleigh quotient gives
\[\bar d=\frac{\mathbf{e}^T\mathbf{A}\mathbf{e}}{\mathbf{e}^T\mathbf{e}}\le\lambda_{\max}\le\Delta,\]
where \(\bar d=2|E|/n\) is the average degree and \(\Delta\) the maximum degree: the lower bound is the Rayleigh quotient evaluated at \(\mathbf{x}=\mathbf{e}\) (a valid, if not necessarily optimal, test vector), and the upper bound follows because every row of \(\mathbf{A}\) sums to at most \(\Delta\).
Since \(\mathbf{A}\) has nonnegative entries, the Perron–Frobenius theorem applies: its eigenvalue of largest absolute value is real, nonnegative, and has a nonnegative eigenvector; if \(G\) is connected, \(\mathbf{A}\) is irreducible, so this eigenvalue is simple and its eigenvector \(\mathbf{v}_1\) (the Perron vector) has strictly positive entries. Every other eigenvector, being orthogonal to a strictly positive vector, must have both positive and negative entries — a fact used again below.
Bipartiteness and the Symmetric Spectrum
A graph is bipartite if its vertices split into two sets \(V_1,V_2\) such that every edge has one endpoint in each. Bipartiteness is exactly reflected in the spectrum:
Claim: \(G\) is bipartite if and only if its spectrum is symmetric about \(0\), i.e. \(\lambda\) occurs as an eigenvalue exactly as often as \(-\lambda\) does.
If \(G\) is bipartite with parts \(V_1,V_2\), let \(\mathbf{S}\) be the diagonal sign matrix with \(s_{ii}=1\) for \(i\in V_1\) and \(s_{ii}=-1\) for \(i\in V_2\) (so \(\mathbf{S}^2=\mathbf{I}\)). Since every edge crosses between \(V_1\) and \(V_2\), flipping the sign of exactly one endpoint of every nonzero entry gives \(\mathbf{SAS}=-\mathbf{A}\). If \(\mathbf{Av}=\lambda\mathbf{v}\), then
\[\mathbf{A}(\mathbf{Sv})=-\mathbf{SAv}=-\lambda(\mathbf{Sv}),\]
so \(\mathbf{Sv}\) is an eigenvector for \(-\lambda\): every eigenvalue's negative is an eigenvalue too, with matching multiplicity, since \(\mathbf{S}\) is invertible. A path on four vertices illustrates the claim: its spectrum is \(\bigl\{\varphi,\ \varphi-1,\ 1-\varphi,\ -\varphi\bigr\}\) with \(\varphi=\frac{1+\sqrt5}{2}\), symmetric about \(0\), consistent with a path being bipartite (odd cycles, by contrast, are never bipartite and never have a symmetric spectrum).
The Moore Bound: How Dense Can a Graph Be?
Counting Walks in a Graph of Diameter Two
Fix a degree \(d\ge2\) and ask: among all \(d\)-regular graphs of diameter at most \(2\) (any two vertices connected by a path of at most two edges), how many vertices \(n\) can such a graph have at most? Building the graph outward from a single vertex, it has \(1\) vertex at distance \(0\), \(d\) neighbors at distance \(1\), and at most \(d(d-1)\) vertices at distance \(2\) (each of the \(d\) neighbors can lead to at most \(d-1\) further, not-yet-seen vertices, since one of its \(d\) edges already goes back to the start). This gives the Moore bound
\[n\le 1+d+d(d-1)=d^2+1,\]
with equality only if none of the distance-\(2\) vertices coincide and no two neighbors of a vertex are themselves adjacent (otherwise fewer than \(d-1\) new vertices would be reached from at least one of them). A graph meeting the bound with equality is called a Moore graph; it necessarily has no triangles and no \(4\)-cycles, since either would create a shortcut that reduces the count of distinct vertices at distance \(2\).
In such an extremal graph, every pair of distinct, non-adjacent vertices then has exactly one common neighbor (not zero, since the diameter is \(2\); not more than one, since that would again reduce the vertex count below the bound), while every pair of adjacent vertices has none (no triangles). Since \((\mathbf{A}^2)_{ij}\) counts common neighbors of \(i\) and \(j\) for \(i\ne j\), and \((\mathbf{A}^2)_{ii}=d\) (one return trip through each of the \(d\) edges at \(i\)), this becomes a clean matrix identity: writing \(\mathbf{J}\) for the \(n\times n\) all-ones matrix,
\[\mathbf{I}+\mathbf{A}+\mathbf{A}^2-d\mathbf{I}=\mathbf{J}.\]
Indeed, on the diagonal both sides equal \(1+0+d-d=1\); off the diagonal, adjacent pairs contribute \(0+1+0=1\) and non-adjacent pairs contribute \(0+0+1=1\), matching \(\mathbf{J}\) everywhere.
An Eigenvalue Equation from the Trace
Apply both sides of this identity to an eigenvector. For \(\mathbf{e}\) itself, \(\mathbf{Ae}=d\mathbf{e}\) and \(\mathbf{A}^2\mathbf{e}=d^2\mathbf{e}\), and \(\mathbf{Je}=n\mathbf{e}\), so the identity just reproduces \(n=d^2+1\), consistent with what is already known. The interesting case is any other eigenvector \(\mathbf{v}\) of \(\mathbf{A}\), with eigenvalue \(\lambda\ne d\). Because \(\mathbf{A}\) is symmetric, \(\mathbf{v}\) can be chosen orthogonal to \(\mathbf{e}\), so \(\mathbf{Jv}=\mathbf{0}\). The identity applied to \(\mathbf{v}\) then gives
\[\mathbf{v}+\lambda\mathbf{v}+\lambda^2\mathbf{v}-d\mathbf{v}=\mathbf{0}\quad\Longrightarrow\quad \lambda^2+\lambda+(1-d)=0,\]
so every eigenvalue other than \(d\) is one of the two roots
\[\lambda_{\pm}=\frac{-1\pm\sqrt{4d-3}}{2}.\]
Now bring in the trace: since the graph has no self-loops, \(\operatorname{tr}(\mathbf{A})=0\), and the trace also equals the sum of the eigenvalues. Writing \(m_+\) and \(m_-\) for the multiplicities of \(\lambda_+\) and \(\lambda_-\) (so \(m_++m_-=n-1=d^2\)),
\[d+m_+\lambda_++m_-\lambda_-=0.\]
If \(\sqrt{4d-3}\) is irrational, \(\lambda_+\) and \(\lambda_-\) are conjugate irrationals, which forces \(m_+=m_-\) (otherwise the sum could not come out to the rational number \(-d\)); substituting \(m_+=m_-=d^2/2\) and \(\lambda_++\lambda_-=-1\) collapses the trace equation to \(d-d^2/2=0\), i.e. \(d=2\) (discarding \(d=0\), which cannot have diameter \(2\) at all, since it describes a single vertex). The only Moore graph in this branch is therefore the \(5\)-cycle (\(d=2\), \(n=5\)), whose adjacency spectrum is \(\bigl\{2,\ \tfrac{-1+\sqrt5}{2}\ (\times2),\ \tfrac{-1-\sqrt5}{2}\ (\times2)\bigr\}\), matching \(\lambda_\pm=\frac{-1\pm\sqrt{4\cdot2-3}}{2}=\frac{-1\pm\sqrt5}{2}\) exactly.
If instead \(\sqrt{4d-3}=s\) is a (necessarily odd) integer, the trace equation becomes a Diophantine constraint relating \(d=\frac{s^2+3}{4}\), \(n=d^2+1\) and the multiplicity \(m_+\); working it through (elementary but tedious algebra, omitted here) reduces it to a quintic in \(s\) whose only integer roots dividing the constant term are \(s=1,3,5,15\), giving exactly four candidate degrees:
The Known Moore Graphs
- \(s=1\): \(d=1\), \(n=2\) — a single edge, which has diameter \(1\), not \(2\), and is discarded;
- \(s=3\): \(d=3\), \(n=10\) — realized by the Petersen graph, with eigenvalues \(3\) (once), \(1\) (five times, matching \(\lambda_+=\frac{-1+3}{2}=1\)) and \(-2\) (four times, matching \(\lambda_-=\frac{-1-3}{2}=-2\));
- \(s=5\): \(d=7\), \(n=50\) — realized by the Hoffman–Singleton graph, with eigenvalues \(7\) (once), \(2\) (twenty-eight times) and \(-3\) (twenty-one times);
- \(s=15\): \(d=57\), \(n=3250\) — whether a graph with these parameters exists at all is, as of this writing, an open problem.
This case analysis and its four solutions are due to Hoffman and Singleton, who introduced the argument to study exactly this question—how large a graph of a given degree and diameter can possibly be—in a 1960 paper that also gave the resulting bound \(n\le d^2+1\) its name, the Moore bound (after Edward F. Moore, who first posed the question). The Petersen graph case can be checked directly: it is \(3\)-regular, every vertex reaches every other vertex within two steps, and \(3^2+1=10\) is exactly its vertex count, so it saturates the bound.
The Graph Laplacian
A second matrix associated with \(G\) is often more convenient than the adjacency matrix: the Laplacian \(\mathbf{L}=\mathbf{D}-\mathbf{A}\), where \(\mathbf{D}=\operatorname{diag}(d_1,\ldots,d_n)\) is the diagonal degree matrix. For any vector \(\mathbf{x}\in\mathbb{R}^n\),
\[\mathbf{x}^T\mathbf{L}\mathbf{x}=\sum_{\{i,j\}\in E}(x_i-x_j)^2,\]
which follows by expanding \(\mathbf{x}^T\mathbf{D}\mathbf{x}=\sum_i d_ix_i^2\) and \(\mathbf{x}^T\mathbf{A}\mathbf{x}=2\sum_{\{i,j\}\in E}x_ix_j\) and regrouping term by term, with each edge contributing \(x_i^2+x_j^2-2x_ix_j=(x_i-x_j)^2\). Since this sum of squares can never be negative, \(\mathbf{L}\) is positive semidefinite, so all of its eigenvalues are \(\ge0\); and \(\mathbf{Le}=\mathbf{0}\) (a constant vector makes every term \((x_i-x_j)^2\) vanish), so \(0\) is always an eigenvalue, with eigenvector \(\mathbf{e}\).
Connectivity and the Algebraic Connectivity
The multiplicity of the eigenvalue \(0\) equals the number of connected components of \(G\): on each component, the quadratic form can only vanish for vectors that are constant on that component (any two adjacent vertices in the same component must agree, and connectivity propagates that equality across the whole component), so there is exactly one such independent direction per component. In particular, for a connected graph the eigenvalue \(0\) is simple, and the second-smallest Laplacian eigenvalue \(\mu_2>0\) is called the graph's algebraic connectivity (a name introduced by Miroslav Fiedler in 1973, so it is also called the Fiedler value); the larger it is, the harder the graph is to disconnect, and its eigenvector (the Fiedler vector) is routinely used to split a graph into two well-connected halves by sorting vertices along it and cutting at the sign change — a simple but effective spectral clustering heuristic. Two disjoint triangles, for instance, have Laplacian spectrum \(\{0,0,3,3,3,3\}\): the eigenvalue \(0\) occurring with multiplicity \(2\) correctly reports two connected components.
A Spectral Bound on the Chromatic Number
The chromatic number \(\chi(G)\) is the minimum number of colors needed to color the vertices so that no edge connects two vertices of the same color. Hoffman showed (1970) that it can be bounded below purely from the adjacency spectrum:
\[\chi(G)\ge1-\frac{\lambda_{\max}}{\lambda_{\min}},\]
where \(\lambda_{\max}\) and \(\lambda_{\min}\) are the largest and smallest eigenvalues of \(\mathbf{A}\) (note \(\lambda_{\min}\le0\), so the fraction is subtracted as a negative quantity, making the bound larger than \(1\)). Intuitively, a proper coloring decomposes \(\mathbf{A}\) into blocks with zero diagonal blocks (no edges within a color class); a short argument using Cauchy's interlacing theorem then bounds how negative an eigenvalue such a decomposition can produce, in terms of the number of blocks used. On the Petersen graph, \(\lambda_{\max}=3\) and \(\lambda_{\min}=-2\), so the bound gives \(\chi(G)\ge1-\tfrac{3}{-2}=2.5\), i.e. \(\chi(G)\ge3\) after rounding up to an integer — and the Petersen graph's chromatic number is indeed exactly \(3\), so the bound is tight in this case.
The chromatic number can also be bounded from the other side, using the clique number \(\omega(G)\), the size of the largest set of pairwise adjacent vertices; trivially \(\chi(G)\ge\omega(G)\), since every vertex of a maximum clique needs a color of its own. Restricting \(\mathbf{A}\) to the rows and columns of such a clique gives the principal submatrix \(\mathbf{J}-\mathbf{I}\) of a complete graph \(K_{\omega(G)}\), whose eigenvalues are \(\omega(G)-1\) (once) and \(-1\) (with multiplicity \(\omega(G)-1\)); by Cauchy's interlacing theorem the largest eigenvalue of \(\mathbf{A}\) itself can only be at least as large as that of any principal submatrix, so
\[\lambda_{\max}\ge\omega(G)-1,\]
with equality exactly for complete graphs, which already saturate it (\(K_n\) has \(\lambda_{\max}=n-1\) and \(\omega(K_n)=n\)).
Coloring greedily, one vertex at a time, never needs more than \(\Delta+1\) colors, since every vertex has at most \(\Delta\) already-colored neighbors, leaving one of \(\Delta+1\) colors free. Since \(\lambda_{\max}\le\Delta\), a sharper bound replaces \(\Delta\) with \(\lambda_{\max}\): Wilf's theorem (1967) states
\[\chi(G)\le\lfloor\lambda_{\max}\rfloor+1.\]
The proof is an induction on \(|V|\): since the average degree is at most \(\lambda_{\max}\), some vertex has degree at most \(\lfloor\lambda_{\max}\rfloor\); removing it leaves a principal submatrix whose largest eigenvalue, by Cauchy's interlacing theorem, is no larger than \(\lambda_{\max}\), so by induction the rest of the graph can be colored with \(\lfloor\lambda_{\max}\rfloor+1\) colors, and the removed vertex can be given one of those same colors, since at most \(\lfloor\lambda_{\max}\rfloor\) of its neighbors already used one. A star graph with \(4\) leaves shows how much sharper this can be than the greedy bound: its maximum degree is \(\Delta=4\) (greedy bound \(5\)), yet its largest eigenvalue is only \(\lambda_{\max}=2\) (Wilf bound \(3\)), much closer to its true, bipartite chromatic number \(2\).
Strongly Regular Graphs and the Friendship Theorem
A \(d\)-regular graph is called strongly regular if there are constants \(a,b\) such that any two adjacent vertices have exactly \(a\) common neighbors, and any two non-adjacent vertices have exactly \(b\) common neighbors (the Moore graphs above are the special strongly regular case \(a=0\), \(b=1\)). The same trace technique used for the Moore bound applies more generally to strongly regular graphs and underlies a striking classical result, the Friendship Theorem (Erdős, Rényi and Sós, 1966): if a finite graph has the property that every two vertices have exactly one common neighbor, it must contain a vertex adjacent to all others.
The idea, in outline, is to first show that any two non-adjacent vertices have the same degree (both are common neighbors of the same collection of pairs), and then to rule out the regular case with an eigenvalue/trace argument entirely analogous to the one above, which forces the degree to satisfy \(d=k^2+1\) for the argument to close, and then \(k\mid k^2+1\) forces \(k=1\), i.e. a triangle. Any graph that is not regular and has the one-common-neighbor property must therefore contain a universal vertex directly. The extremal examples are the windmill graphs, built from \(k\) triangles all sharing a single common vertex; the smallest non-trivial case, two triangles glued at a vertex, has five vertices, one of degree \(4\) and four of degree \(2\), and every pair among its five vertices indeed shares exactly one common neighbor.
Interlacing at Work: Huang's Proof of the Sensitivity Conjecture
Interlacing is not merely a bookkeeping tool for graph invariants; in 2019 it supplied the missing step in a \(27\)-year-old open problem from theoretical computer science, the sensitivity conjecture (Nisan and Szegedy, 1992), which asks whether two natural measures of how sensitive a Boolean function is to flipping single input bits — its sensitivity and the more permissive block sensitivity — are always polynomially related. Hao Huang settled the conjecture with a short proof about a purely graph-theoretic object, the hypercube.
The hypercube graph \(Q_d\) has vertex set \(\{0,1\}^d\), with an edge between two vertices whenever they differ in exactly one bit, so every vertex has degree \(d\); \(Q_3\) already looks like the familiar geometric cube:
Huang's argument uses a cleverly signed variant of the adjacency matrix rather than \(Q_d\)'s adjacency matrix itself. Define \(\mathbf{A}_1=\begin{pmatrix}0&1\\1&0\end{pmatrix}\) and, recursively,
\[\mathbf{A}_d=\begin{pmatrix}\mathbf{A}_{d-1}&\mathbf{I}\\\mathbf{I}&-\mathbf{A}_{d-1}\end{pmatrix},\]
a \(2^d\times2^d\) symmetric matrix whose entrywise absolute value is exactly the adjacency matrix of \(Q_d\) (only some edges pick up a minus sign). Squaring it block by block,
\[\mathbf{A}_d^2=\begin{pmatrix}\mathbf{A}_{d-1}^2+\mathbf{I}&\mathbf{0}\\\mathbf{0}&\mathbf{A}_{d-1}^2+\mathbf{I}\end{pmatrix},\]
so by induction \(\mathbf{A}_d^2=d\mathbf{I}\) (the base case \(\mathbf{A}_1^2=\mathbf{I}\) is immediate). Every eigenvalue of \(\mathbf{A}_d\) therefore equals \(\pm\sqrt d\), and since \(\operatorname{tr}(\mathbf{A}_d)=0\), exactly half of its \(2^d\) eigenvalues, i.e. \(2^{d-1}\) of them, equal \(+\sqrt d\) and the other half \(-\sqrt d\).
Now let \(H\) be an induced subgraph of \(Q_d\) on more than half the vertices, \(|V_H|\ge2^{d-1}+1\), and let \(\mathbf{B}\) be the corresponding \(|V_H|\times|V_H|\) principal submatrix of \(\mathbf{A}_d\). Since only \(2^d-|V_H|<2^{d-1}\) rows and columns were removed, Cauchy's interlacing theorem guarantees \(\lambda_{\max}(\mathbf{B})\ge\lambda_{2^{d-1}}(\mathbf{A}_d)\), and because the top \(2^{d-1}\) eigenvalues of \(\mathbf{A}_d\) all equal \(+\sqrt d\), this gives \(\lambda_{\max}(\mathbf{B})\ge\sqrt d\). Since every entry of \(\mathbf{B}\) has absolute value at most \(1\), the same row-sum argument used above for \(\lambda_{\max}\le\Delta\) applies to \(\mathbf{B}\)'s entrywise absolute values as well, giving \(\lambda_{\max}(\mathbf{B})\le\Delta(H)\), the maximum degree within \(H\) itself. Combining the two bounds,
\[\Delta(H)\ge\sqrt d,\]
a strikingly clean conclusion (Huang, 2019) given that \(H\) is only assumed to contain more than half of \(Q_d\)'s vertices. A reduction due to Gotsman and Linial (1992) translates exactly this graph-theoretic statement into the sensitivity conjecture, so Huang's theorem completes its proof: sensitivity and block sensitivity are indeed polynomially related for every Boolean function.
Applications of Spectral Graph Theory
- Spectral clustering and graph partitioning via the Fiedler vector of the Laplacian
- Expander graphs, whose eigenvalue gap \(d-\lambda_2\) controls how well-mixed random walks on them are, with applications to derandomization and robust network design
- PageRank and related centrality measures, which rank vertices by the Perron vector of a suitably normalized adjacency (transition) matrix
- Estimating the chromatic number and independence number of a graph from its spectrum alone, without exhaustively searching colorings
- Detecting the number of connected components, and how loosely or tightly they are joined, from the small end of the Laplacian spectrum