How statement and proof provenance work
The first chip identifies the source of the statement or construction; the second identifies the source of its local proof or verification.
- Literature-sourced: the exact statement appears in a cited source; only wording and notation differ.
- AI-adapted: a semantically identical restatement of literature-sourced material, modulo indexing, notation, and boundary cases adopted by the library.
- AI-generated: a genuinely novel statement formulated by AI, with no source for the claim itself.
These labels describe origin, not correctness: citations and verification chips remain separate evidence.
The multiplicity of the Laplacian eigenvalue equals the number of connected components
Statement
Let be a finite simple graph with Laplacian matrix , and let be its connected components. Then
Since is real symmetric, this is equivalently the multiplicity of the eigenvalue of .
Facts & Assumptions
Given: A finite simple graph with Laplacian matrix and connected components .
The connected components of partition (The connected components of a graph partition its vertex set and are its maximal connected subgraphs).
A connected component is a maximal connected induced subgraph (Connected graphs and connected components defined by the existence of vertex paths).
The Laplacian has diagonal entries and off-diagonal entries exactly on adjacent vertex pairs (The Laplacian matrix of a finite simple graph).
The Laplacian is positive semidefinite and annihilates the all-ones vector (The Laplacian is positive semidefinite and sends the all-ones vector to zero).
A real symmetric matrix has an orthogonal basis of eigenvectors, so for such a matrix the geometric and algebraic multiplicities of an eigenvalue agree (Real spectral theorem: a self-adjoint endomorphism of a finite-dimensional real inner product space has an orthonormal eigenbasis).
Proof
For a vector , the Laplacian quadratic form is , because expanding groups the diagonal terms by degrees and subtracts each edge contribution twice. Therefore, if , then [L2] gives , so every summand vanishes and on every edge. Conversely, if is constant on every edge, then for each vertex every neighbor of satisfies , so [F2] gives . Hence .
By [F1], a function on is constant on every edge exactly when it is constant on each connected component. By [L1], the indicator vectors are linearly independent and every vector constant on components is a linear combination of them. So step 1.1 shows that these indicator vectors form a basis of , and hence .
The final equivalence with multiplicity of the eigenvalue follows from [L3], because is real symmetric.
Depends on
- Connected graphs and connected components defined by the existence of vertex paths
- The connected components of a graph partition its vertex set and are its maximal connected subgraphs
- The Laplacian matrix of a finite simple graph
- The Laplacian is positive semidefinite and sends the all-ones vector to zero
- Real spectral theorem: a self-adjoint endomorphism of a finite-dimensional real inner product space has an orthonormal eigenbasis
Used by
Dependency tree · two levels
17 results within two dependency steps of this one, each drawn at its shortest distance from it. An arrow runs from a result to what uses it, so the chart reads left to right and ends at this result, which carries a heavier outline. Every node is a link to that result. Click elsewhere on the chart to enlarge it.
Sources
- Richard P. Stanley, MIT 18.314 handout, The Matrix-Tree Theorem (standard reference, not scraped)