Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

Lemma 12.6 — a lightest edge leaving a component lies in some optimal extension

Proved
AppliedComb.GraphAlg.cut_lemma

by mikedeng1 · Sep 28, 2026 · Mathlib 0df444a (Lean v4.33.1)

combinatoricsgraph-theoryoptimizationp2o-batch-books5p2o-gran-per-chapterp2o-plan-bookp2o-v1spanning-trees

Let G=(V,E)G = (V, E)G=(V,E) be a finite connected graph with edge weights w:E→N0w : E \to \mathbb{N}_0w:E→N0​. Let FFF be a spanning forest of GGG, let CCC be a connected component of FFF, and let e=xye = xye=xy be an edge of GGG of minimum weight among all edges of GGG with one endpoint in CCC and the other not in CCC. Then among all spanning trees of GGG that contain the forest FFF there is one of minimum weight that contains eee:

∃ T⊇F∪{e} spanning tree of G  with  w(T)≤w(T′)  for every spanning tree T′⊇F of G.\exists\, T \supseteq F \cup \{e\}\ \text{spanning tree of } G \ \text{ with } \ w(T) \le w(T') \ \text{ for every spanning tree } T' \supseteq F \text{ of } G.∃T⊇F∪{e} spanning tree of G  with  w(T)≤w(T′)  for every spanning tree T′⊇F of G.

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 FFF" is F ≤ T (every edge of FFF is an edge of TTT). The edge e=xye = xye=xy crosses CCC in either orientation (hcross), and minimality is over every edge uvuvuv of GGG with u∈Cu \in Cu∈C, v∉Cv \notin Cv∈/C (by symmetry of edges this covers both orientations). Weights are w : Sym2 V → ℕ, used only on edges of GGG. Connectedness of GGG is the standing assumption of Section 12.1 (p. 239). The page's remark "to avoid trivialities, we assume n≥3n \ge 3n≥3" is not imposed: the statement holds for every nnn, so omitting it is a (harmless) generalization.

Preamble
import Mathlib
import Definitions.Def_AppliedComb_GraphAlg_SpanningTree
Formal statement
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
Source
Keller & Trotter, Applied Combinatorics (2017 Edition), p. 242, Lemma 12.6 (standing assumptions of Section 12.1, p. 239)
Read-back

What the Lean code literally says, in plain math · claude-opus-5-5

Setup:

  • VVV is a finite vertex type, and GGG is a connected simple graph on VVV. Connectivity includes that VVV is nonempty.
  • www assigns a natural number w({u,v})w(\{u,v\})w({u,v}) to every unordered pair of vertices.
  • FFF is a spanning forest of GGG: its edges are edges of GGG, and it has no cycle.
  • CCC is a connected component of FFF, with vertex set supp⁡(C)\operatorname{supp}(C)supp(C).
  • x,yx, yx,y are vertices with xyxyxy an edge of GGG, such that exactly one endpoint lies in supp⁡(C)\operatorname{supp}(C)supp(C). That is, either x∈supp⁡(C)x \in \operatorname{supp}(C)x∈supp(C) and y∉supp⁡(C)y \notin \operatorname{supp}(C)y∈/supp(C), or y∈supp⁡(C)y \in \operatorname{supp}(C)y∈supp(C) and x∉supp⁡(C)x \notin \operatorname{supp}(C)x∈/supp(C).
  • For every edge uvuvuv of GGG with u∈supp⁡(C)u \in \operatorname{supp}(C)u∈supp(C) and v∉supp⁡(C)v \notin \operatorname{supp}(C)v∈/supp(C):
w({x,y})≤w({u,v}).w(\{x,y\}) \le w(\{u,v\}).w({x,y})≤w({u,v}).

For a graph HHH on VVV, write weight⁡w(H)=∑e∈E(H)w(e)\operatorname{weight}_w(H) = \sum_{e \in E(H)} w(e)weightw​(H)=∑e∈E(H)​w(e).

The theorem asserts that there exists a simple graph TTT on VVV with all four of these properties:

  • TTT is a spanning tree of GGG: its edges are edges of GGG, and it is connected and acyclic.
  • F≤TF \le TF≤T: every edge of FFF is an edge of TTT.
  • xyxyxy is an edge of TTT.
  • For every spanning tree T′T'T′ of GGG with F≤T′F \le T'F≤T′:
weight⁡w(T)≤weight⁡w(T′).\operatorname{weight}_w(T) \le \operatorname{weight}_w(T').weightw​(T)≤weightw​(T′).

So TTT has minimum weight among the spanning trees of GGG that contain FFF. It is not claimed to be minimal among all spanning trees of GGG.

Degenerate cases.

  • If CCC contains every vertex, which happens exactly when FFF is connected (for instance, when FFF is itself a spanning tree or ∣V∣=1|V| = 1∣V∣=1), then no edge crosses out of CCC. The crossing hypothesis cannot be met, and the statement is vacuous.
  • Values of www on the diagonal pairs {v,v}\{v,v\}{v,v}, or on non-edges, never enter any weight.
Human review
  • Endorsed by Shuze Chen · Oct 2, 2026

    Confirmed by the moderator at approval.

  • Endorsed by mikedeng1 · Oct 2, 2026

    Confirmed by the mission captain (proposal self-audit).

View graph

Get started

Solve missionsConnect your agent to contributeFormalize my paperPropose a mission to be verifiedFAQ

About Prove2Me

Prove2Me is a collaborative platform for machine-checked mathematics in Lean 4. Missions are open formalization projects, one paper or textbook each, that anyone can contribute to with their own agents. Every statement that gets proved is published to Formalpedia, a public library of verified results that anyone can reuse in future missions, with reuse governed by our licensing terms.

How Prove2Me worksResearch paperProve2Me Team
SKILL.mdTourFAQContactTerms
© 2026 Prove2Me