Proposition 12.3 — edges and components of a spanning forest
ProvedAppliedComb.GraphAlg.spanning_forest_edgesLet be a graph on vertices and let be a spanning forest of . Then
if then has exactly connected components, and in particular is a spanning tree of if and only if .
This is the counting fact behind both minimum spanning tree algorithms of the chapter: a spanning forest grows into a spanning tree exactly when it reaches edges.
Formalization Note. is Fintype.card V, is Nat.card H.edgeSet, and the number of components is Nat.card H.ConnectedComponent. The hypothesis is written to avoid truncated subtraction in ; the lower bound is automatic. The book's upper bound presupposes , which is the hypothesis 0 < n.
import Mathlib import Definitions.Def_AppliedComb_GraphAlg_SpanningTree
namespace AppliedComb.GraphAlg
/-- Keller–Trotter, p. 240, Proposition 12.3. Let `G = (V, E)` be a graph on `n` vertices and
`H = (V, S)` a spanning forest. Then `0 ≤ |S| ≤ n − 1`; if `|S| = n − k` then `H` has `k`
components; in particular `H` is a spanning tree iff it has `n − 1` edges. `|S| = n − k` is
written `|S| + k = n` (no truncated subtraction); `n ≥ 1` as the bound `|S| ≤ n − 1` requires. -/
theorem spanning_forest_edges {V : Type*} [Fintype V] (G H : SimpleGraph V) (n : ℕ)
(hn : Fintype.card V = n) (hpos : 0 < n) (hH : IsSpanningForest G H) :
Nat.card H.edgeSet ≤ n - 1 ∧
(∀ k : ℕ, Nat.card H.edgeSet + k = n → Nat.card H.ConnectedComponent = k) ∧
(IsSpanningTree G H ↔ Nat.card H.edgeSet = n - 1) := by sorry
end AppliedComb.GraphAlg
Read-back
What the Lean code literally says, in plain math · claude-opus-5-5
Setup:
- is a finite vertex type, and is a natural number with and .
- and are simple graphs on .
- is a spanning forest of : every edge of is an edge of , and contains no cycle.
Write for the number of edges of , and for the number of connected components of . The theorem asserts all three of the following.
- For every natural number : if , then .
- is a spanning tree of if and only if . Being a spanning tree means: every edge of is an edge of , and is connected, acyclic, and has a nonempty vertex set.
Since , the subtraction is ordinary subtraction. In item 2 at most one can satisfy the hypothesis, namely .
Degenerate cases.
- The empty vertex type is excluded by .
- For , the assertions say three things: has edges; if then has exactly one component; and is a spanning tree of exactly when it has edges.
- Item 2 says nothing for any with .
- enters only through the hypothesis that 's edges lie in , and through the containment requirement in the definition of spanning tree.
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.