The Laplacian matrix counts connected components
ProvedFamousTheorems.laplacian_kernel_connected_componentsThe Laplacian matrix counts connected components. Let be a finite simple graph with Laplacian matrix , where is the diagonal degree matrix and the adjacency matrix. Then the number of connected components of equals .
Equivalently, the multiplicity of as an eigenvalue of is the number of components, and is connected exactly when the second smallest eigenvalue is positive. This is the starting point of spectral graph theory and of spectral clustering.
Formalization note. Mathlib's SimpleGraph.card_connectedComponent_eq_finrank_ker_toLin'_lapMatrix. G.lapMatrix ℝ is the Laplacian, and Matrix.toLin' turns it into a linear map on .
Preamble
import Mathlib
Formal statement
namespace FamousTheorems
theorem laplacian_kernel_connected_components {V : Type*} [Fintype V] [DecidableEq V] (G : SimpleGraph V) [DecidableRel G.Adj] :
Fintype.card G.ConnectedComponent = Module.finrank ℝ (LinearMap.ker (Matrix.toLin' (G.lapMatrix ℝ))) := by sorry
end FamousTheoremsSource
Listed in Mathlib's curated theorem manifests (docs/1000.yaml); formalized in Mathlib as `SimpleGraph.card_connectedComponent_eq_finrank_ker_toLin'_lapMatrix`. Proof here reduces to that Mathlib result.