Algebraic Connectivity As A Test For Connectedness

Why the Second Laplacian Eigenvalue Matters

A graph can have many edges and still fail to be connected: an isolated vertex, for example, is enough to separate one part of a graph from the rest. The Laplacian matrix records local edge information, but its eigenvalues reveal a global fact. For a graph with at least two vertices, its second-smallest Laplacian eigenvalue is positive exactly when the graph is connected. This eigenvalue is called the algebraic connectivity.

Throughout, graphs are finite, simple and undirected. A graph is connected if every pair of vertices can be joined by a path. Write $n=|V(G)|$, let $\mathbf{A}(G)$ be the adjacency matrix, and let $\mathbf{D}(G)$ be the diagonal matrix whose entry at vertex $v$ is $\deg(v)$. The Laplacian is $\mathbf{L}(G)=\mathbf{D}(G)-\mathbf{A}(G)$. Since this matrix is real and symmetric, its eigenvalues are real; list them with multiplicity in nondecreasing order:

\lambda_1\leq \lambda_2\leq\cdots\leq\lambda_n.

In particular, repeated eigenvalues appear repeatedly in this list. Thus, if the smallest eigenvalue has multiplicity two, then $\lambda_1=\lambda_2=0$; “second-smallest” does not mean “second distinct eigenvalue.”

Definition: For a graph $G$ with $n\geq2$, its algebraic connectivity is $a(G)=\lambda_2$, where $\lambda_2$ is the second-smallest eigenvalue of $\mathbf{L}(G)$, counted with multiplicity.

Edge Energy and the Laplacian Kernel

For a real vector $x$ indexed by the vertices, write $x_v$ for its coordinate at $v$. The Laplacian quadratic form is the sum of squared differences across edges:

x^{\mathsf T}\mathbf{L}(G)x = \sum_{uv\in E(G)}(x_u-x_v)^2.

Indeed, the degree-matrix part contributes $\sum_{v\in V(G)}\deg(v)x_v^2$, while the adjacency-matrix part contributes $-2\sum_{uv\in E(G)}x_ux_v$. In the degree sum, each edge $uv$ contributes $x_u^2+x_v^2$. Combining these terms edge by edge gives the displayed sum. It follows that $\mathbf{L}(G)$ is positive semidefinite: $x^{\mathsf T}\mathbf{L}(G)x\geq0$ for every $x$, so all its eigenvalues are nonnegative.

Proposition: The vectors in the nullspace of $\mathbf{L}(G)$ are exactly those that are constant on each connected component of $G$. Consequently, the dimension of this nullspace is the number of connected components.

Proof. If $\mathbf{L}(G)x=0$, then $x^{\mathsf T}\mathbf{L}(G)x=0$. The edge-energy identity expresses this quantity as a sum of nonnegative squares. The sum is zero only if $x_u=x_v$ for every edge $uv$. Along any path, these equalities imply that the coordinates at its endpoints agree. Thus $x$ is constant on each connected component. Conversely, if $x$ is constant on each component, then $x_u=x_v$ for every edge, so the edge-energy identity gives $x^{\mathsf T}\mathbf{L}(G)x=0$. Since $\mathbf{L}(G)$ is positive semidefinite, the spectral theorem implies $x^{\mathsf T}\mathbf{L}(G)x=0$ only when $\mathbf{L}(G)x=0$. Finally, the vectors that are constant on each component have one freely chosen constant per component, so this space has dimension equal to the number of components. $\square$

The all-ones vector $\mathbf{1}$ is in the nullspace, because it is constant on every component. The proposition gives more: the multiplicity of the zero eigenvalue is exactly the number of components, including isolated vertices as components of size one.

The Connectedness Criterion

Theorem: If $G$ has $n\geq2$ vertices, then $G$ is connected if and only if $a(G)=\lambda_2>0$.

Proof. By the proposition, the multiplicity of the zero eigenvalue of $\mathbf{L}(G)$ equals the number of connected components. If $G$ is connected, this multiplicity is one. All eigenvalues are nonnegative, so $\lambda_1=0$ and $\lambda_2>0$. If $G$ is disconnected, it has at least two components, so zero has multiplicity at least two. Hence $\lambda_1=\lambda_2=0$, and $a(G)$ is not positive. These implications prove the equivalence. $\square$

The restriction $n\geq2$ matters. A one-vertex graph is connected, but its Laplacian has just one eigenvalue, so a second-smallest eigenvalue is not defined. The definition of $a(G)$ above therefore applies only when there are at least two vertices. The empty graph also has no second-smallest eigenvalue under this definition.

Rayleigh Quotient Interpretation

The eigenvalue $\lambda_2$ has a variational interpretation that explains why it detects disconnection. For a nonzero vector $x$, the Rayleigh quotient is $x^{\mathsf T}\mathbf{L}(G)x/(x^{\mathsf T}x)$. The following characterization uses vectors perpendicular to the all-ones vector, meaning $\sum_{v\in V(G)}x_v=0$.

Proposition: For $n\geq2$, $$ \lambda_2= \min_{\substack{x\ne 0\\x^{\mathsf T}\mathbf{1}=0}} \frac{x^{\mathsf T}\mathbf{L}(G)x}{x^{\mathsf T}x} = \min_{\substack{x\ne 0\\\sum_v x_v=0}} \frac{\sum_{uv\in E(G)}(x_u-x_v)^2}{\sum_v x_v^2}. $$

Proof. The spectral theorem for real symmetric matrices gives an orthonormal basis of eigenvectors of $\mathbf{L}(G)$. Choose the first eigenvector to be $\mathbf{1}/\sqrt n$, which has eigenvalue zero. Expand any vector $x$ perpendicular to $\mathbf{1}$ in the remaining orthonormal eigenvectors, say $x=\sum_{i=2}^n c_iq_i$, where $\mathbf{L}(G)q_i=\lambda_iq_i$. Then $x^{\mathsf T}x=\sum_{i=2}^n c_i^2$ and $x^{\mathsf T}\mathbf{L}(G)x=\sum_{i=2}^n\lambda_i c_i^2$. Since each $\lambda_i\geq\lambda_2$, the quotient is at least $\lambda_2$. Equality is attained by taking $x=q_2$, which is nonzero and perpendicular to $\mathbf{1}$. Substituting the edge-energy identity gives the second expression. If zero has multiplicity greater than one, an eigenvector for a second zero eigenvalue supplies $q_2$, so the same argument still applies. $\square$

Thus $a(G)$ is the smallest possible edge energy per unit squared length among nonzero vectors whose coordinates sum to zero. If the graph is disconnected, a nonconstant vector can be constant on each component and have coordinate sum zero; its edge energy is zero. If the graph is connected, the theorem says that every such nonzero vector has positive edge energy, and the minimum is positive.

Worked Example: The Three-Vertex Path

Let $G$ have vertex set $V(G)=\{1,2,3\}$ and edge set $E(G)=\{12,23\}$. In the vertex order $1,2,3$, its Laplacian is

\mathbf{L}(G)= \begin{pmatrix} 1&-1&0\\ -1&2&-1\\ 0&-1&1 \end{pmatrix}.

Rather than relying on a decimal approximation to the roots of a characteristic polynomial, check three independent eigenvectors. For $u_1=(1,1,1)^{\mathsf T}$, multiplication gives $\mathbf{L}u_1=(0,0,0)^{\mathsf T}=0u_1$. For $u_2=(1,0,-1)^{\mathsf T}$, it gives $\mathbf{L}u_2=(1,0,-1)^{\mathsf T}=1u_2$. For $u_3=(1,-2,1)^{\mathsf T}$, it gives $\mathbf{L}u_3=(3,-6,3)^{\mathsf T}=3u_3$. These three nonzero vectors are mutually perpendicular, so they form a basis and give all three eigenvalues.

In increasing order the eigenvalues are $0,1,3$, so $a(G)=1$. The graph is connected, consistent with the criterion. As a Rayleigh-quotient check, $u_2$ has coordinate sum $1+0-1=0$, energy $(1-0)^2+(0-(-1))^2=1+1=2$, and squared length $1^2+0^2+(-1)^2=2$. Its quotient is $2/2=1$, equal to $\lambda_2$.

Worked Example: The Complete Graph on Three Vertices

Let $G$ have vertex set $V(G)=\{1,2,3\}$ and edge set $E(G)=\{12,13,23\}$. Each vertex has degree $2$, so

\mathbf{L}(G)= \begin{pmatrix} 2&-1&-1\\ -1&2&-1\\ -1&-1&2 \end{pmatrix}.

For $u_1=(1,1,1)^{\mathsf T}$, each row sums to zero, so $\mathbf{L}u_1=0u_1$. For $u_2=(1,-1,0)^{\mathsf T}$, multiplication gives $(3,-3,0)^{\mathsf T}=3u_2$. For $u_3=(1,1,-2)^{\mathsf T}$, it gives $(3,3,-6)^{\mathsf T}=3u_3$. These vectors are nonzero and mutually perpendicular, so the full eigenvalue list is $0,3,3$.

Therefore $a(G)=3>0$, as expected because every pair of vertices is joined by an edge. For an independent quotient check, $u_2$ has coordinate sum $1-1+0=0$. Its edge energy is $(1-(-1))^2+(1-0)^2+((-1)-0)^2=4+1+1=6$; its squared length is $1+1+0=2$. The quotient is $6/2=3$.

Worked Example: An Edge and an Isolated Vertex

Let $G$ have vertex set $V(G)=\{1,2,3\}$ and edge set $E(G)=\{12\}$. Vertex $3$ is isolated. In the vertex order $1,2,3$,

\mathbf{L}(G)= \begin{pmatrix} 1&-1&0\\ -1&1&0\\ 0&0&0 \end{pmatrix}.

For $u_1=(1,1,1)^{\mathsf T}$, multiplication gives zero. For $u_2=(1,1,-2)^{\mathsf T}$, it also gives zero, so the eigenvalue zero occurs at least twice. For $u_3=(1,-1,0)^{\mathsf T}$, multiplication gives $(2,-2,0)^{\mathsf T}=2u_3$. These three mutually perpendicular vectors form a basis, hence the eigenvalues are $0,0,2$. Thus $a(G)=0$, and the graph is disconnected. As a quotient check, $u_2$ has sum $1+1-2=0$ and nonzero squared length $1+1+4=6$; its only edge contributes energy $(1-1)^2=0$, so its quotient is $0/6=0=\lambda_2$.

What the Test Does—and a Common Mistake

For a graph with at least two vertices, computing $\lambda_2$ gives a direct yes-or-no test: positivity means connected, and zero means disconnected. The Rayleigh quotient adds an interpretation: it measures the least edge energy among mean-zero vertex assignments, relative to the squared length of the assignment. This is why the eigenvalue detects whether the graph splits into components: values can be constant within each component, yet differ between components without creating any energy across an edge.

Common mistake: testing the smallest eigenvalue. The smallest Laplacian eigenvalue is zero for every nonempty graph, because the all-ones vector is in the nullspace. For the three-vertex path above, the eigenvalues are $0,1,3$. The incorrect calculation “$\lambda_1=0$, therefore the graph is disconnected” gives the wrong conclusion. The correction is to use the second eigenvalue: here $\lambda_2=1>0$, so the graph is connected. Conversely, the edge-plus-isolate example has $\lambda_2=0$, correctly detecting disconnection.

Check Your Understanding

Use eigenvalues counted with multiplicity, and state when the connectedness criterion applies.

Why must the all-ones vector be an eigenvector of every graph Laplacian, and what is its eigenvalue?
A graph has eigenvalues $0,0,2,4$. What can you conclude about its connected components?
For a mean-zero vector $x$, explain why zero edge energy implies that $x$ is constant on each connected component.
Why is the second-smallest eigenvalue not defined for a graph with one vertex under the definition used here?
For the graph with vertices $\{1,2,3\}$ and edges $\{12,13\}$, use the criterion to predict whether its second-smallest Laplacian eigenvalue is positive, without calculating its exact value.