Lemma 12.6 — a lightest edge leaving a component lies in some optimal extension
ProvedAppliedComb.GraphAlg.cut_lemmaLet be a finite connected graph with edge weights . Let be a spanning forest of , let be a connected component of , and let be an edge of of minimum weight among all edges of with one endpoint in and the other not in . Then among all spanning trees of that contain the forest there is one of minimum weight that contains :
This lemma is what makes greedy constructions of minimum weight spanning trees correct; the book derives the correctness of Kruskal's algorithm (Algorithm 12.8) and Prim's algorithm (Algorithm 12.10) from it.
Formalization Note. "Contains the forest " is F ≤ T (every edge of is an edge of ). The edge crosses in either orientation (hcross), and minimality is over every edge of with , (by symmetry of edges this covers both orientations). Weights are w : Sym2 V → ℕ, used only on edges of . Connectedness of is the standing assumption of Section 12.1 (p. 239). The page's remark "to avoid trivialities, we assume " is not imposed: the statement holds for every , so omitting it is a (harmless) generalization.
import Mathlib import Definitions.Def_AppliedComb_GraphAlg_SpanningTree
namespace AppliedComb.GraphAlg
/-- Keller–Trotter, p. 242, Lemma 12.6. `G` is a connected graph with edge weights
`w : E → ℕ₀` (the standing assumptions of Section 12.1, p. 239). Let `F` be a spanning forest of
`G`, `C` a component of `F`, and `e = xy` an edge of minimum weight among all edges with one
endpoint in `C` and the other not in `C`. Then among all spanning trees of `G` that contain `F`
there is one of minimum weight that contains `e`. -/
theorem cut_lemma {V : Type*} [Fintype V] (G : SimpleGraph V) (hG : G.Connected)
(w : Sym2 V → ℕ) (F : SimpleGraph V) (hF : IsSpanningForest G F)
(C : F.ConnectedComponent) (x y : V) (hxy : G.Adj x y)
(hcross : (x ∈ C.supp ∧ y ∉ C.supp) ∨ (y ∈ C.supp ∧ x ∉ C.supp))
(hmin : ∀ u v : V, G.Adj u v → u ∈ C.supp → v ∉ C.supp → w s(x, y) ≤ w s(u, v)) :
∃ T : SimpleGraph V, IsSpanningTree G T ∧ F ≤ T ∧ T.Adj x y ∧
∀ T' : SimpleGraph V, IsSpanningTree G T' → F ≤ T' → weight w T ≤ weight w T' := 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 connected simple graph on . Connectivity includes that is nonempty.
- assigns a natural number to every unordered pair of vertices.
- is a spanning forest of : its edges are edges of , and it has no cycle.
- is a connected component of , with vertex set .
- are vertices with an edge of , such that exactly one endpoint lies in . That is, either and , or and .
- For every edge of with and :
For a graph on , write .
The theorem asserts that there exists a simple graph on with all four of these properties:
- is a spanning tree of : its edges are edges of , and it is connected and acyclic.
- : every edge of is an edge of .
- is an edge of .
- For every spanning tree of with :
So has minimum weight among the spanning trees of that contain . It is not claimed to be minimal among all spanning trees of .
Degenerate cases.
- If contains every vertex, which happens exactly when is connected (for instance, when is itself a spanning tree or ), then no edge crosses out of . The crossing hypothesis cannot be met, and the statement is vacuous.
- Values of on the diagonal pairs , or on non-edges, never enter any weight.
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.