Questions: Graph Laplacian and Spectral Properties

Question 1

A graph has 3 connected components. How many zero eigenvalues does its Laplacian matrix have?

• A. 1 — the all-ones vector is always in the null space, giving exactly one zero eigenvalue
• B. 0 — a graph with multiple components is not well-defined for Laplacian analysis
• C. 3 — the number of zero eigenvalues equals the number of connected components
• D. It depends on the number of edges, not the number of components

Answer: (C)

Each connected component contributes exactly one zero eigenvalue to the Laplacian, with a corresponding eigenvector that is 1 on the vertices of that component and 0 elsewhere. For a single connected graph, only the global all-ones vector is in the null space (one zero eigenvalue). For three components, there are three independent all-ones-on-component vectors in the null space. This means you can determine graph connectivity just by counting zero eigenvalues — no BFS or DFS required.

Question 2

Graph A has a Fiedler value (λ₂) near zero; Graph B has a large Fiedler value. Both have the same number of vertices and edges. Which claim is best supported?

• A. Graph A is better connected than B, since a small eigenvalue means more stable dynamics
• B. Graph A has a near-bottleneck — a small cut set of edges whose removal would nearly disconnect it; Graph B is well-connected with many independent paths
• C. Graph B has more spanning trees than A, since larger eigenvalues indicate more edges
• D. Both graphs must be identical in connectivity since they have the same number of edges

Answer: (B)

The Fiedler value measures algebraic connectivity: large λ₂ means the graph is robust and well-connected with many independent paths between most vertex pairs. Small λ₂ (near zero) means the graph is close to being disconnected — there is a bottleneck where a small edge cut would fragment it. The Fiedler vector corresponding to λ₂ encodes the near-optimal partition split, which is why λ₂ and its eigenvector are the basis of spectral graph partitioning and spectral clustering.

Question 3

Since L·1 = 0 (the most-ones vector is in the Laplacian's null space), nearly every graph — connected or not — has exactly one zero eigenvalue.

• T. True
• F. False

Answer: False

For a connected graph, there is exactly one zero eigenvalue, corresponding to the global all-ones vector. For a disconnected graph with k components, there are k zero eigenvalues — one per component — because each component contributes its own independent null-space vector (1 on its vertices, 0 elsewhere). Counting zero eigenvalues is precisely how the Laplacian encodes connectivity information.

Question 4

The eigenvector corresponding to the Fiedler value (second-smallest eigenvalue of the Laplacian) can be used to partition a graph into two groups with few inter-group edges — the basis of spectral clustering.

• T. True
• F. False

Answer: True

The Fiedler vector assigns a real value to each vertex. By partitioning vertices into those with positive values and those with negative values (or by threshold), you obtain two groups with approximately minimal edge cut between them. This is not an exact solution to the NP-hard minimum cut problem, but the Fiedler vector gives a near-optimal relaxed solution. This spectral approach is widely used in network analysis, image segmentation, and machine learning.

Question 5

Why does the graph Laplacian L = D − A always have 0 as an eigenvalue, and what property of the graph does the number of zero eigenvalues reveal?

Model answer: L always has 0 as an eigenvalue because the all-ones vector 1 satisfies L·1 = 0: for each row i, the diagonal entry is deg(i) and each off-diagonal entry is −1 for each neighbor, so the sum is deg(i) − deg(i) = 0. The number of zero eigenvalues equals the number of connected components in the graph, because each component contributes one independent null-space vector.

This is a beautiful example of algebra encoding topology: a purely algebraic object (the eigenvalue count of a matrix) reveals a topological property (connectivity) without any explicit graph traversal. It also motivates why the Laplacian appears in so many contexts — electrical networks, heat diffusion, PageRank — because zero eigenvalues correspond to 'conserved quantities' or 'equilibrium modes' of whatever dynamics the graph represents.