Why the Laplacian Detects Connectivity
A graph can be disconnected even when its vertices are all included in one matrix. The graph Laplacian records the links between vertices, and its nullspace reveals which vertices are tied together by paths. In particular, a vector in that nullspace must assign the same value to vertices joined by an edge. Following paths then forces it to be constant throughout each connected component.
We work with a finite undirected weighted graph on vertices \(1,\dots,n\). Each edge \(\{i,j\}\) has a positive real weight \(w_{ij}=w_{ji}\); pairs that are not edges have weight zero. An unweighted graph is the special case in which every edge has weight \(1\). A path from one vertex to another is a sequence of vertices in which consecutive vertices share an edge. Vertices are in the same connected component when there is a path between them. An isolated vertex, with no incident edges, forms a component by itself.
Let \(a_{ij}=w_{ij}\) when \(\{i,j\}\) is an edge and \(a_{ij}=0\) otherwise, and let \(d_i=\sum_{j=1}^n a_{ij}\) be the weighted degree of vertex \(i\). The adjacency matrix \(\mathbf{A}\) has entries \(a_{ij}\), and the degree matrix \(\mathbf{D}\) is diagonal with entries \(d_i\). The (weighted, undirected) graph Laplacian is \(\mathbf{L}=\mathbf{D}-\mathbf{A}\).
The Sum-of-Squares Identity
The key calculation uses undirectedness: \(a_{ij}=a_{ji}\). For any column vector \(\mathbf{x}=(x_1,\dots,x_n)^\top\), the Laplacian’s quadratic expression can be grouped by edges.
Proof. By \(\mathbf{L}=\mathbf{D}-\mathbf{A}\), the diagonal term is \(\mathbf{x}^{\top}\mathbf{D}\mathbf{x}=\sum_i d_i x_i^2\), and the adjacency term is \(\mathbf{x}^{\top}\mathbf{A}\mathbf{x}=\sum_{i,j}a_{ij}x_ix_j\). Each undirected edge \(\{i,j\}\) of weight \(w_{ij}\) contributes \(w_{ij}x_i^2+w_{ij}x_j^2\) to the first sum, because its weight is included in both \(d_i\) and \(d_j\). It contributes \(w_{ij}x_ix_j+w_{ij}x_jx_i=2w_{ij}x_ix_j\) to the second sum. Subtracting these contributions gives \(w_{ij}(x_i^2-2x_ix_j+x_j^2)=w_{ij}(x_i-x_j)^2\). Summing over all edges gives the identity. \(\square\)
Every term on the right is nonnegative, since each weight is positive and each squared difference is nonnegative. Therefore, if \(\mathbf{L}\mathbf{x}=\mathbf{0}\), then \(\mathbf{x}^{\top}\mathbf{L}\mathbf{x}=0\), and the sum of these nonnegative terms is zero. In that case every edge must join vertices with equal entries. The converse also matters: if entries agree across every edge, each row of \(\mathbf{L}\mathbf{x}\) is zero because that row sums the weighted differences between the vertex and its neighbours.
Nullspace and Connected Components
Proof. First suppose \(\mathbf{L}\mathbf{x}=\mathbf{0}\). The sum-of-squares identity gives $$ 0=\mathbf{x}^{\top}\mathbf{L}\mathbf{x} =\sum_{\{i,j\}\text{ an edge}}w_{ij}(x_i-x_j)^2. $$ Every summand is nonnegative and every edge weight is positive, so each edge satisfies \(x_i=x_j\). If two vertices are in the same component, there is a path joining them. Equality across each consecutive edge of that path implies that the entries at its endpoints are equal. Thus \(\mathbf{x}\) is constant on each component.
Conversely, suppose \(\mathbf{x}\) is constant on each component. Every edge joins vertices in the same component, so \(x_i=x_j\) for each edge \(\{i,j\}\). In row \(i\), the product \((\mathbf{L}\mathbf{x})_i\) is \(\sum_j a_{ij}(x_i-x_j)\), which is zero because every term with \(a_{ij}\ne0\) has \(x_i=x_j\). This also holds for an isolated vertex, whose row has no nonzero terms. Hence \(\mathbf{L}\mathbf{x}=\mathbf{0}\).
For each component \(C_r\), the indicator vector \(\mathbf{1}_{C_r}\) is constant on every component, so it lies in the nullspace by the direction just proved. These vectors are linearly independent: if \(\sum_{r=1}^k c_r\mathbf{1}_{C_r}=\mathbf{0}\), choose a vertex in \(C_s\). At that vertex the sum has value \(c_s\), since the components are disjoint, so \(c_s=0\). This holds for every \(s\). Finally, any vector constant on each component, with value \(c_r\) on \(C_r\), equals \(\sum_{r=1}^k c_r\mathbf{1}_{C_r}\). Thus the indicators span the nullspace and form a basis. A basis of \(k\) vectors has dimension \(k\), giving \(\operatorname{nullity}\mathbf{L}=k\). \(\square\)
Worked Examples
Worked Example: A Path and an Isolated Vertex
Consider four vertices with edges \(\{1,2\}\) and \(\{2,3\}\), each of weight \(1\); vertex \(4\) is isolated. Find the components and the Laplacian nullspace.
The degrees are \(d_1=1\), \(d_2=2\), \(d_3=1\), and \(d_4=0\). Thus $$ \mathbf{L}= \begin{bmatrix} 1&-1&0&0\\ -1&2&-1&0\\ 0&-1&1&0\\ 0&0&0&0 \end{bmatrix}. $$ The components are \(C_1=\{1,2,3\}\) and \(C_2=\{4\}\). The theorem predicts that the nullspace consists of vectors \((c,c,c,d)^\top\), with basis $$ \mathbf{1}_{C_1}= \begin{bmatrix}1\\1\\1\\0\end{bmatrix}, \qquad \mathbf{1}_{C_2}= \begin{bmatrix}0\\0\\0\\1\end{bmatrix}. $$
To check directly, the equation \(\mathbf{L}\mathbf{x}=\mathbf{0}\) gives \(x_1-x_2=0\), \(-x_1+2x_2-x_3=0\), and \(-x_2+x_3=0\); its fourth equation is \(0=0\). The first and third equations give \(x_1=x_2=x_3\), and then the second is satisfied. There is no restriction on \(x_4\). Multiplying the displayed basis vectors by \(\mathbf{L}\) gives $$ \mathbf{L}\mathbf{1}_{C_1}= \begin{bmatrix}1-1\\-1+2-1\\-1+1\\0\end{bmatrix} =\mathbf{0}, \qquad \mathbf{L}\mathbf{1}_{C_2}= \begin{bmatrix}0\\0\\0\\0\end{bmatrix} =\mathbf{0}. $$ These checks agree with the two-component count and show \(\operatorname{nullity}\mathbf{L}=2\).
Worked Example: Six Vertices and Three Components
Consider six vertices with edges \(\{1,2\}\) of weight \(2\), \(\{2,3\}\) of weight \(1\), and \(\{4,5\}\) of weight \(3\). Vertex \(6\) is isolated. Form the Laplacian and identify its nullspace.
The weighted degrees are \(2,3,1,3,3,0\), respectively. The Laplacian is $$ \mathbf{L}= \begin{bmatrix} 2&-2&0&0&0&0\\ -2&3&-1&0&0&0\\ 0&-1&1&0&0&0\\ 0&0&0&3&-3&0\\ 0&0&0&-3&3&0\\ 0&0&0&0&0&0 \end{bmatrix}. $$ The components are \(\{1,2,3\}\), \(\{4,5\}\), and \(\{6\}\). For \(\mathbf{x}=(x_1,\dots,x_6)^\top\), the first, third, and fourth equations of \(\mathbf{L}\mathbf{x}=\mathbf{0}\) give $$ 2(x_1-x_2)=0,\qquad x_3-x_2=0,\qquad 3(x_4-x_5)=0. $$ Therefore \(x_1=x_2=x_3\) and \(x_4=x_5\); the second equation is then \(-2x_1+3x_2-x_3=0\), and the fifth equation is \(-3x_4+3x_5=0\), so both are satisfied. The sixth equation imposes no restriction on \(x_6\).
Thus the nullspace vectors have the form \((a,a,a,b,b,c)^\top\). Its component-indicator basis is $$ \mathbf{1}_{\{1,2,3\}}= \begin{bmatrix}1\\1\\1\\0\\0\\0\end{bmatrix}, \quad \mathbf{1}_{\{4,5\}}= \begin{bmatrix}0\\0\\0\\1\\1\\0\end{bmatrix}, \quad \mathbf{1}_{\{6\}}= \begin{bmatrix}0\\0\\0\\0\\0\\1\end{bmatrix}. $$ Multiplication checks each one: the first two entries of \(\mathbf{L}\mathbf{1}_{\{1,2,3\}}\) are \(2-2=0\) and \(-2+3-1=0\), and the third is \(-1+1=0\); all other entries are zero. For \(\mathbf{1}_{\{4,5\}}\), the fourth and fifth entries are \(3-3=0\) and \(-3+3=0\), and the remaining entries are zero. The last vector is in the nullspace because row 6 is zero. The three basis vectors give \(\operatorname{nullity}\mathbf{L}=3\), matching the three components.
Worked Example: A Connected Weighted Network
Take four vertices with edges \(\{1,2\}\) of weight \(2\), \(\{2,3\}\) of weight \(1\), and \(\{2,4\}\) of weight \(3\). Find the nullspace and verify the component count.
The degrees are \(2,6,1,3\), so $$ \mathbf{L}= \begin{bmatrix} 2&-2&0&0\\ -2&6&-1&-3\\ 0&-1&1&0\\ 0&-3&0&3 \end{bmatrix}. $$ Every vertex can be reached from vertex \(2\), so the graph is connected. The first, third, and fourth equations in \(\mathbf{L}\mathbf{x}=\mathbf{0}\) give \(2(x_1-x_2)=0\), \(x_3-x_2=0\), and \(3(x_4-x_2)=0\). Hence \(x_1=x_2=x_3=x_4\). Substituting a constant vector \((c,c,c,c)^\top\) into the remaining, second equation gives \(-2c+6c-c-3c=0\), so every constant vector is a solution.
A basis is \(\mathbf{1}=(1,1,1,1)^\top\). Indeed, $$ \mathbf{L}\mathbf{1}= \begin{bmatrix}2-2\\-2+6-1-3\\-1+1\\-3+3\end{bmatrix} =\begin{bmatrix}0\\0\\0\\0\end{bmatrix}. $$ The equations show there are no other forms of nullspace vector, so the nullity is \(1\), as expected for one connected component.
Using Nullity as a Component Count
The theorem gives a practical conclusion: for a Laplacian built from a finite undirected graph with positive edge weights, finding \(\operatorname{nullity}\mathbf{L}\) gives the number of connected components. The nullspace gives more information than the count alone: each basis indicator identifies which vertices belong to one component. If the components are already known, their indicators provide a direct basis; if the Laplacian is given, solving \(\mathbf{L}\mathbf{x}=\mathbf{0}\) reveals which vertex entries must agree.
This conclusion depends on the stated graph assumptions. The sum-of-squares argument uses symmetry of the edge weights and their positivity. The result is about the Laplacian of an undirected graph; do not apply it unchanged to an arbitrary directed network matrix. Isolated vertices are included, not discarded: each contributes a zero row and a separate component-indicator vector.
Common Pitfall: Counting Zero Rows
A zero row is not the same thing as a component. For example, the connected path with edges \(\{1,2\}\) and \(\{2,3\}\), both of weight \(1\), has $$ \mathbf{L}= \begin{bmatrix}1&-1&0\\-1&2&-1\\0&-1&1\end{bmatrix}. $$ A wrong conclusion would be: “There are no zero rows, so the nullity is zero.” But direct multiplication gives \(\mathbf{L}(1,1,1)^\top=\mathbf{0}\), so the nullity is not zero.
To determine it, row-reduce the matrix: $$ \begin{bmatrix}1&-1&0\\-1&2&-1\\0&-1&1\end{bmatrix} \xrightarrow{R_2\to R_2+R_1} \begin{bmatrix}1&-1&0\\0&1&-1\\0&-1&1\end{bmatrix} \xrightarrow{R_3\to R_3+R_2} \begin{bmatrix}1&-1&0\\0&1&-1\\0&0&0\end{bmatrix} \xrightarrow{R_1\to R_1+R_2} \begin{bmatrix}1&0&-1\\0&1&-1\\0&0&0\end{bmatrix}. $$ The equations are \(x_1=x_3\) and \(x_2=x_3\), so the nullspace consists of constant vectors and has dimension \(1\). The graph has one component. Count the dimension of the solution space, not the zero rows in the original Laplacian.
Check Your Understanding
Use the sum-of-squares identity and the component-indicator description to justify your answers.
- Why must the entries of a nullspace vector agree at the endpoints of every positive-weight edge?
- A graph has components \(\{1,2\}\), \(\{3\}\), and \(\{4,5,6\}\). Write a basis for the Laplacian nullspace and state its nullity.
- What does an isolated vertex contribute to the Laplacian nullspace, and why?
- For a connected graph, what is the nullity of its Laplacian? Explain using the component-indicator basis.
- Why does the argument require the graph to be undirected with positive edge weights?
