Laplacian Nullspaces And Connected Components

What the Laplacian Kernel Records

The graph Laplacian turns a question about how vertices are joined into a question about a matrix equation. In particular, the equation $Lx=0$ detects which vertices belong to the same connected component: a solution must assign equal values to vertices that can be joined by a path, while different components may have different values. Thus the dimension of the nullspace gives the number of connected components.

Throughout, $G=(V,E)$ is a finite simple undirected graph. Write $n=|V|$ and $m=|E|$. Vectors have real coordinates indexed by $V$, so $x\in\mathbb{R}^{V}$ has a coordinate $x_v$ for each vertex $v$. The degree matrix $\mathbf{D}$ is diagonal with $\mathbf{D}_{vv}=\deg(v)$, and the adjacency matrix $\mathbf{A}$ has entry $1$ when its two distinct indices are adjacent and $0$ otherwise. The Laplacian is $\mathbf{L}=\mathbf{D}-\mathbf{A}$.

Definition: The nullspace of $\mathbf{L}$ is $\ker\mathbf{L}=\{x\in\mathbb{R}^{V}:\mathbf{L}x=0\}$. A connected component is a maximal set of vertices in which every pair is joined by a path; isolated vertices are components of size one. A vector is constant on a component if all its coordinates at vertices of that component are equal.

For every vertex $v$, the $v$-coordinate of $\mathbf{L}x$ can also be written as a sum of differences between the value at $v$ and the values at its neighbors:

(\mathbf{L}x)_v=\deg(v)x_v-\sum_{u\in N(v)}x_u =\sum_{u\in N(v)}(x_v-x_u).

This expression suggests that a vector in the nullspace should have no change across edges. The quadratic form makes that implication precise.

The Edge-Energy Identity

Proposition: For every real vector $x\in\mathbb{R}^{V}$, $$ x^{\mathsf T}\mathbf{L}x=\sum_{uv\in E}(x_u-x_v)^2. $$

Proof. Since $\mathbf{L}=\mathbf{D}-\mathbf{A}$, expanding the matrix product gives $x^{\mathsf T}\mathbf{L}x=\sum_{v\in V}\deg(v)x_v^2-\sum_{u,v\in V}\mathbf{A}_{uv}x_ux_v$. In the first sum, each edge $uv$ contributes $x_u^2+x_v^2$, because it contributes once to the degree of each endpoint. In the second sum, the undirected edge $uv$ contributes $x_ux_v$ from the ordered pair $(u,v)$ and another $x_vx_u$ from $(v,u)$. Its total contribution to the difference is therefore $x_u^2+x_v^2-2x_ux_v=(x_u-x_v)^2$. Summing these contributions over all edges proves the identity. If $E$ is empty, both sums are zero, so the identity also holds in that case. $\square$

Every term on the right is nonnegative. Consequently, if the energy is zero, each edge has endpoints with equal coordinates. Conversely, if coordinates agree across every edge, every term in the energy sum vanishes. The next theorem uses this fact to describe the entire nullspace.

The Nullspace and the Components

Theorem: Let $G$ be a finite simple undirected graph with $c$ connected components. A vector $x\in\mathbb{R}^{V}$ belongs to $\ker\mathbf{L}$ if and only if it is constant on each connected component. In particular, $\dim(\ker\mathbf{L})=c$.

Proof. First suppose $x\in\ker\mathbf{L}$, so $\mathbf{L}x=0$. Then $x^{\mathsf T}\mathbf{L}x=0$. By the edge-energy identity, $\sum_{uv\in E}(x_u-x_v)^2=0$. Each summand is nonnegative, and a finite sum of nonnegative real numbers is zero only if every summand is zero. Thus $x_u=x_v$ for every edge $uv$. If $u$ and $v$ lie in the same component, there is a path from $u$ to $v$. Equality across each successive edge of that path gives $x_u=x_v$. Hence $x$ is constant on every component.

For the converse, suppose $x$ is constant on each component. Every neighbor $u$ of a vertex $v$ lies in the same component as $v$, so $x_u=x_v$. Using the coordinate formula, $(\mathbf{L}x)_v=\sum_{u\in N(v)}(x_v-x_u)=0$ for every vertex $v$. Thus $\mathbf{L}x=0$, and $x\in\ker\mathbf{L}$.

To count the dimension, let the components be $C_1,\ldots,C_c$. For each $i$, define the indicator vector $\mathbf{1}_{C_i}$ to have coordinate $1$ on $C_i$ and $0$ elsewhere. Each such vector is constant on every component, so the converse just proved puts it in $\ker\mathbf{L}$. These vectors are linearly independent: in a relation $\sum_{i=1}^{c}a_i\mathbf{1}_{C_i}=0$, examining a vertex in $C_j$ gives $a_j=0$, since that vertex belongs to $C_j$ and no other component. They also span the kernel: if $x$ has constant value $a_i$ on $C_i$, then $x=\sum_{i=1}^{c}a_i\mathbf{1}_{C_i}$. Thus they form a basis and the nullity is $c$. If $V=\varnothing$, there are no components and $\mathbb{R}^{V}$ is the zero-dimensional vector space; its nullspace has dimension $0$, so the same conclusion holds. $\square$

The theorem distinguishes two statements that are easy to confuse. A constant vector on all vertices is always in the kernel, but for a disconnected graph the kernel can contain vectors that take different values on different components. One independent choice of value is available for each component.

Worked Calculations

Worked Example: A Path and an Isolated Vertex

Let $G=(V,E)$ have $V=\{1,2,3,4\}$ and $E=\{12,23\}$. The components are $\{1,2,3\}$ and $\{4\}$: vertices $1,2,3$ are joined by the path $1,2,3$, and vertex $4$ has no incident edge. The degrees are $1,2,1,0$, respectively. In the vertex order $1,2,3,4$, the Laplacian is

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

For $x=(x_1,x_2,x_3,x_4)^{\mathsf T}$, the equation $\mathbf{L}x=0$ gives the four equations $x_1-x_2=0$, $-x_1+2x_2-x_3=0$, $-x_2+x_3=0$, and $0=0$. The first and third give $x_1=x_2=x_3$; substituting into the second gives $-x_1+2x_1-x_1=0$, as required. There is no condition on $x_4$. Therefore every solution is $x=(a,a,a,b)^{\mathsf T}$, where $a,b\in\mathbb{R}$.

Check: The vectors $(1,1,1,0)^{\mathsf T}$ and $(0,0,0,1)^{\mathsf T}$ give the two component indicators. Multiplying the displayed matrix by either vector gives the zero vector, and the two vectors are independent. Thus the nullity is $2$, matching the component count.

Worked Example: A Connected Cycle

Let $G=(V,E)$ have $V=\{1,2,3,4\}$ and $E=\{12,23,34,14\}$, the cycle $C_4$. Each vertex has degree $2$, and the graph is connected because the cycle gives a path between any two of its vertices. Its Laplacian is

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

For any $x\in\ker\mathbf{L}$, the energy identity gives $0=x^{\mathsf T}\mathbf{L}x=(x_1-x_2)^2+(x_2-x_3)^2+(x_3-x_4)^2+(x_1-x_4)^2$. Every square is nonnegative, so all four differences are zero. Hence $x_1=x_2=x_3=x_4=a$ for some real number $a$. Conversely, multiplying the matrix by $(a,a,a,a)^{\mathsf T}$ gives four coordinates $2a-a-a=0$, $-a+2a-a=0$, $-a+2a-a=0$, and $-a-a+2a=0$. The kernel is exactly the one-dimensional space of constant vectors.

Check: The four listed edges form one connected cycle, so $c=1$. The calculation gives one free parameter $a$, hence nullity $1$, in agreement with the theorem.

Worked Example: Two Separate Edges

Let $G=(V,E)$ have $V=\{1,2,3,4,5\}$ and $E=\{12,34\}$. Its components are $\{1,2\}$, $\{3,4\}$, and $\{5\}$. In the vertex order shown, the Laplacian is

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

The first two rows of $\mathbf{L}x=0$ give $x_1-x_2=0$ and $-x_1+x_2=0$, so $x_1=x_2$. The third and fourth rows give $x_3=x_4$, and the last row imposes no condition on $x_5$. Thus the general solution is $x=(a,a,b,b,d)^{\mathsf T}$, with $a,b,d\in\mathbb{R}$.

Check: The three independent component indicators are $(1,1,0,0,0)^{\mathsf T}$, $(0,0,1,1,0)^{\mathsf T}$, and $(0,0,0,0,1)^{\mathsf T}$. Matrix multiplication gives zero for each: the first edge block gives $1-1=0$ in both rows, the second gives $1-1=0$ in both rows, and the isolated-vertex row is zero. There are three components and three independent kernel vectors.

Common Pitfall and Why the Result Matters

Pitfall: assuming every kernel vector is globally constant. In the last example, take $a=3$, $b=-2$, and $d=5$, so $x=(3,3,-2,-2,5)^{\mathsf T}$. Direct multiplication gives first coordinate $3-3=0$, second coordinate $-3+3=0$, third coordinate $-2-(-2)=0$, fourth coordinate $-(-2)+(-2)=0$, and fifth coordinate $0$. Hence $\mathbf{L}x=0$, although the coordinates are not all equal. The mistaken conclusion that every kernel vector must be one global constant overlooks disconnectedness: the values agree within each component, but can differ between components.

The component-indicator basis also explains why nullity is a useful structural quantity. Solving a linear system for $\ker\mathbf{L}$ reveals exactly how many connected pieces the graph has, including isolated vertices. A connected graph has nullity $1$; a graph with $c$ components has nullity $c$. For the graph with no vertices, there are no components and the nullity is $0$. These conclusions require no assumption that the graph is connected or has any edges.

Check Your Understanding

Use the edge-energy identity and the component-indicator description to justify your answers.

For $V=\{1,2,3,4\}$ and $E=\{12,34\}$, write a basis for $\ker\mathbf{L}$ and give its dimension.
Why does $\mathbf{L}x=0$ imply equality of coordinates at the endpoints of every edge?
For a connected graph with at least one vertex, what is the dimension of $\ker\mathbf{L}$, and why?
Explain why an isolated vertex contributes one to the nullity.
What are the number of components and the nullity when $V=\varnothing$?