Algebraic connectivity λ₂, Fiedler eigenvector, and cut quality
—λ₂ (Fiedler)
—Spectral cut
—Random cut
—Improvement
—Vertices
Fiedler vector: The eigenvector corresponding to the second-smallest eigenvalue λ₂ of the graph Laplacian L = D − A. Sign of each entry assigns each vertex to a partition. λ₂ = 0 means the graph is disconnected. Algebraic connectivity: λ₂ measures how well-connected the graph is. Cheeger's inequality: h(G) ≤ √(2λ₂) where h is the edge expansion (ratio cut bound).
Spectral bisection consistently outperforms random cuts, especially for structured graphs like grids and barbells where natural cluster structure exists.