Questions: Graph Laplacian and Laplacian Spectrum

Question 1

A researcher computes the Laplacian matrix of an undirected graph and finds that three of its eigenvalues are exactly 0. What does this tell you about the graph's structure?

• A. The graph has three vertices with degree 0 (isolated vertices)
• B. The graph has three connected components
• C. The graph has three edges that form a cycle
• D. The algebraic connectivity is 3, indicating a highly robust graph

Answer: (B)

The number of zero eigenvalues of the Laplacian equals the number of connected components. A connected graph has exactly one zero eigenvalue (the trivial constant eigenvector); a graph with k components has k zero eigenvalues, one for each component. This is not the same as counting isolated vertices (though isolated vertices do create components). Three zero eigenvalues mean the graph consists of exactly three disconnected subgraphs — you cannot travel between the three groups along any path. This algebraic test for connectivity is one of the Laplacian's most powerful properties.

Question 2

Two graphs, A and B, are analyzed for network robustness. Graph A has algebraic connectivity λ₂ = 0.03; Graph B has λ₂ = 2.4. Which graph is more vulnerable to disconnection if edges are removed, and why?

• A. Graph A is more robust — a smaller second eigenvalue means vertices are more tightly clustered
• B. Graph B is more vulnerable — larger λ₂ creates unstable spectral properties
• C. Graph A is more vulnerable — its small λ₂ indicates a bottleneck structure where two large clusters are connected by few edges
• D. Both are equally vulnerable — algebraic connectivity measures diameter, not edge-cut robustness

Answer: (C)

Algebraic connectivity λ₂ measures how well-connected a graph is. A small λ₂ means the graph has a bottleneck: there exist two large groups of vertices connected by only a thin bridge of edges. Cutting that bridge disconnects the graph. Graph A's λ₂ = 0.03 is very small, indicating such a bottleneck — it is fragile. Graph B's λ₂ = 2.4 indicates densely interconnected vertices with no obvious cut point — much more robust. λ₂ appears in bounds on edge expansion (how many edges must be cut to bisect the graph), making it the canonical measure of network robustness and the central object of expander graph theory.

Question 3

The smallest eigenvalue of the Laplacian matrix is always 0, corresponding to a constant eigenvector across all vertices.

• T. True
• F. False

Answer: True

True. This follows from a fundamental property of the Laplacian: every row sums to zero (because L = D − A, and for each row, the degree entry in D equals the sum of adjacency entries in A). This means the all-ones vector (constant on every vertex) is always an eigenvector with eigenvalue 0. Since the Laplacian is positive semidefinite, 0 is always the minimum eigenvalue. The number of times 0 appears as an eigenvalue counts the connected components, because each component contributes one 'flat' eigenvector that is constant within the component and 0 elsewhere.

Question 4

A large algebraic connectivity (λ₂) indicates that a graph has a bottleneck — a sparse cut that makes it easy to disconnect the graph into two large parts.

• T. True
• F. False

Answer: False

False. A *small* λ₂ indicates a bottleneck; a *large* λ₂ indicates dense, robust connectivity. The Cheeger inequality bounds edge expansion by λ₂: a graph with small λ₂ has low edge expansion, meaning you can separate it into two large parts by cutting relatively few edges. A graph with large λ₂ (like a complete graph or expander) requires cutting many edges to bisect it — it has no bottleneck. Expander graphs, which are specifically designed for robustness and efficient communication, are characterized by having λ₂ that grows with the number of vertices. This direction (large = robust, small = bottleneck) is essential for applying the Laplacian to network analysis.

Question 5

Why does every row of the Laplacian matrix L = D − A sum to zero, and what does this algebraic property reflect about the graph?

Model answer: For any vertex i, the diagonal entry D[i][i] equals the degree of vertex i — the number of edges incident to it. The off-diagonal entries in row i of −A are −1 for each neighbor and 0 otherwise, so there are exactly degree(i) entries of −1. The row sum is thus D[i][i] + (sum of −1s for each neighbor) = degree(i) − degree(i) = 0. This reflects the graph's balance: the Laplacian encodes how much each vertex 'differs' from its neighbors, and in a graph without sources or sinks, every unit of difference into a vertex is matched by an equal unit out.

The zero row-sum property has deep consequences. It means the all-ones vector is always in the null space, guaranteeing at least one zero eigenvalue. It also means the Laplacian governs diffusion processes on the graph (e.g., heat flow, random walks) — the zero row-sum is the discrete analog of conservation: whatever 'flows out' of a vertex must equal what 'flows in' at equilibrium. This connection between the algebraic structure and flow dynamics on the graph is why the Laplacian, not the adjacency matrix, is the natural operator for studying how information, disease, or influence spreads through a network.