Alphabeta Math
TheoremStatement: Literature-sourcedProof: AI-adaptedSession-authored (Fable 5 assisted)precheck passaudited 2026-08-28
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 0 equals the number of connected components

Statement

Let G be a finite simple graph with Laplacian matrix L(G), and let C1,,Cr be its connected components. Then

dimkerL(G)=r.

Since L(G) is real symmetric, this is equivalently the multiplicity of the eigenvalue 0 of L(G).

Facts & Assumptions

Given: A finite simple graph G with Laplacian matrix L and connected components C1,,Cr.

[F1]

A connected component is a maximal connected induced subgraph (Connected graphs and connected components defined by the existence of vertex paths).

[F2]

The Laplacian has diagonal entries deg(v) and off-diagonal entries 1 exactly on adjacent vertex pairs (The Laplacian matrix of a finite simple graph).

[L2]

The Laplacian is positive semidefinite and annihilates the all-ones vector (The Laplacian is positive semidefinite and sends the all-ones vector to zero).

[L3]

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

technique · direct
1.1

For a vector x=(xv)vV(G), the Laplacian quadratic form is xTLx={u,v}E(G)(xuxv)2, because expanding xT(DA)x groups the diagonal terms by degrees and subtracts each edge contribution twice. Therefore, if Lx=0, then [L2] gives 0=xTLx, so every summand vanishes and xu=xv on every edge. Conversely, if x is constant on every edge, then for each vertex u every neighbor v of u satisfies xv=xu, so [F2] gives (Lx)u=deg(u)xuvuxv=0. Hence Lx=0.

F2L2algebra
2.1

By [F1], a function on V(G) is constant on every edge exactly when it is constant on each connected component. By [L1], the indicator vectors 1C1,,1Cr 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 kerL, and hence dimkerL=r.

step 1.1L1F1
3.1

The final equivalence with multiplicity of the eigenvalue 0 follows from [L3], because L is real symmetric.

step 2.1L3

Depends on

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