Kruskal.processEdges_optimal
Optimality of the greedy edge-selection sweep. Let $\mathit{edges}$ be a list of weighted edges on $n$ vertices, sorted in nondecreasing order of weight, and let $\mathit{uf}$ be a union-find state whose induced partition is exactly the reachability relation of some base edge list $\mathit{base}$: for all vertices $a$ and $b$, the representatives $\mathit{uf}(a)$ and $\mathit{uf}(b)$ are equal if and only if $a$ and $b$ are joined by a path through the edges of $\mathit{base}$. Let $S$ be any list of edges, each of which occurs in $\mathit{edges}$, such that merging all of $S$ into $\mathit{uf}$ and merging all of $\mathit{edges}$ into $\mathit{uf}$ yield the same partition of the vertices. Then the greedy sweep — which starts from $\mathit{uf}$, scans $\mathit{edges}$ in order, and keeps each edge exactly when its two endpoints lie in currently distinct components — produces a set of edges whose total weight is at most the total weight of $S$.
Statement
set_option relaxedAutoImplicit false in set_option autoImplicit false in lemma Kruskal.processEdges_optimal {n : ℕ} (edges : List (WEdge n)) (uf : UF n) (base : List (WEdge n)) (huf : ∀ a b : Fin n, uf a = uf b ↔ Reach base a b) (S : List (WEdge n)) (hSsub : ∀ e ∈ S, e ∈ edges) (hSspan : UF.SamePartition (uf.mergeAll S) (uf.mergeAll edges)) (hsorted : List.Pairwise (fun e1 e2 => e1.weight ≤ e2.weight) edges) : totalWeight (processEdges edges uf []) ≤ totalWeight S
- Source
- TCSlib, `Kruskal.processEdges_optimal`
- Lean proof
- By Harsha Polavaram, from github.com/Shilun-Allan-Li/tcslib at
c8a02591b1e5(Copyright (c) 2026 Harsha Polavaram. All rights reserved, Apache-2.0). Compiled here against leanprover/lean4:v4.33.1, Mathlib v4.33.1; written for leanprover/lean4:v4.25.0.Kruskal.processEdges_optimal← Kruskal.processEdges_optimal (TCSlib/GraphTheory/Kruskal/Optimality.lean:86): adapted
What was changed in
Kruskal.processEdges_optimal--- TCSlib/GraphTheory/Kruskal/Optimality.lean:86 (Kruskal.processEdges_optimal) +++ as compiled here @@ -1,2 +1,4 @@ -lemma processEdges_optimal {n : ℕ} +set_option relaxedAutoImplicit false in +set_option autoImplicit false in +lemma Kruskal.processEdges_optimal {n : ℕ} (edges : List (WEdge n)) (uf : UF n) (base : List (WEdge n)) @@ -33,6 +35,6 @@ (by convert mergeAll_perm uf (show List.Perm (S.erase e ++ [e]) - (e :: S.erase e) from by grind) using 1 : + (e :: S.erase e) from by grind) using 1 <;> try rfl : UF.SamePartition (uf.mergeAll (S.erase e ++ [e])) ((uf.merge e.u e.v).mergeAll (S.erase e))).symm - convert hp2.trans ‹_› using 1 + convert hp2.trans ‹_› using 1 <;> try rfl obtain ⟨S', hS'_subset, hS'_span, hS'_weight⟩ := @@ -42,5 +44,6 @@ (by intros a b - convert mergeAll_iff_reach uf base [e] huf a b using 1) + exact mergeAll_iff_reach uf base [e] huf a b) S' hS'_subset hS'_span - linarith [totalWeight_erase S e heS] + linarith [totalWeight_erase S e heS, processEdges_take_weight (e := e) (rest := edges) (uf := uf) + (fun h => he ((huf _ _).1 h))] · obtain ⟨f, hfS, hf⟩ : ∃ f ∈ S, UF.SamePartition @@ -60,6 +63,6 @@ · grind - · refine hf.trans ?_; convert hSspan using 1 + · refine hf.trans ?_; convert hSspan using 1 <;> try rfl · unfold UF.merge; aesop have := ih (uf.merge e.u e.v) (base ++ [e]) - (by convert mergeAll_iff_reach uf base [e] huf using 1) S' hS'sub hS'span + (mergeAll_iff_reach uf base [e] huf) S' hS'sub hS'span have hfedges : f ∈ edges := by @@ -68,2 +71,3 @@ · exact h - linarith [totalWeight_erase S f hfS, hsorted.1 f hfedges] + linarith [totalWeight_erase S f hfS, hsorted.1 f hfedges, processEdges_take_weight (e := e) (rest := edges) (uf := uf) + (fun h => he ((huf _ _).1 h))] - Verified
- 16 Oct 2026
- Axioms
Classical.choiceQuot.soundpropext- Built on 26
- Kruskal.uf_exchangeUnion-find form of the exchange argument. Let $\mathit{uf}\colon \mathrm{Fin}\,n \to \bbn$ be a union-find state whose classes coincide…
- Kruskal.mergeAll_permPermutation invariance of edge merging. Fix $n$ and an initial union-find state $\mathit{uf} : \mathrm{Fin}\,n \to \bbn$. If two lists of…
- Kruskal.mergeAll_iff_reachMerging preserves the reachability invariant. Fix $n$ and let $uf : \mathrm{Fin}\,n \to \bbn$ be a union-find state assigning each of the…
- Kruskal.UFThe union-find state for $n$ nodes is defined as a function $\mathrm{Fin}\,n \to \mathbb{N}$ mapping each node to its current…
- Kruskal.UF.SamePartition$\mathtt{SamePartition}\,\mathit{uf}_1\,\mathit{uf}_2$ holds when two union-find states induce the same equivalence relation on nodes: for…
- Kruskal.UF.find$\mathtt{find}\,\mathit{uf}\,i$ returns the representative of node $i$ in the union-find state $\mathit{uf}$, defined simply as…
- Kruskal.UF.merge$\mathtt{merge}\,\mathit{uf}\,i\,j$ unifies the components of nodes $i$ and $j$ by reassigning every node whose representative equals…
- Kruskal.UF.mergeAll$\mathtt{mergeAll}\,\mathit{uf}\,\mathit{es}$ folds a list of weighted edges $\mathit{es}$ into the union-find $\mathit{uf}$ by calling…
- Kruskal.WEdgeA weighted edge over $n$ vertices is a structure with two endpoints $u, v : \mathrm{Fin}\,n$ and a natural-number weight…
- Kruskal.processEdges$\mathtt{processEdges}\,\mathit{es}\,\mathit{uf}\,\mathit{acc}$ scans the edge list $\mathit{es}$ left-to-right: an edge $e$ is added to…
- Kruskal.reduce_to_restDropping a redundant edge from a candidate set. Let $\mathit{uf}$ be a union-find state on $n$ nodes, let $e$ be a weighted edge with…
- Kruskal.processEdges_skipSkipping an intra-component edge in the sweep. Fix a number of nodes $n$, a union-find state $\mathit{uf} : \mathrm{Fin}\,n \to \bbn$, a…
- Kruskal.processEdges_take_weightWeight contributed by an accepted edge. Fix a natural number $n$ and a union-find state $\mathit{uf}$ over $n$ nodes, and let $e$ be a…
- Kruskal.Reach$\mathtt{Reach}\,\mathit{edges}$ is the reflexive--transitive closure of $\mathtt{SymAdj}\,\mathit{edges}$; that is,…
- Kruskal.totalWeightThe total weight of an edge list is the sum of the weights of all its edges:…
- Kruskal.totalWeight_eraseTotal weight after removing an edge. Let $\mathit{edges}$ be a list of weighted edges over $n$ vertices, and let $e$ be a weighted edge…
- Kruskal.UF.SamePartition.symmSymmetry of the same-partition relation. Fix $n \in \bbn$, and regard a union-find state on $n$ nodes as a function…
- Kruskal.UF.SamePartition.transTransitivity of the same-partition relation. Let $n$ be a natural number, and let…
- Kruskal.erase_append_permMoving a member to the end is a permutation. Let $l$ be a finite list of weighted edges over $n$ vertices, and let $e$ be a weighted edge…
- Kruskal.mergeAll_cons_eqPeeling the leading edge off a merge fold. Let $\mathit{uf} : \mathrm{Fin}\,n \to \bbn$ be a union-find state on $n$ nodes, let $e$ be a…
- Kruskal.merge_noopMerging within a single component leaves the state unchanged. Let $\mathit{uf}\colon \mathrm{Fin}\,n \to \bbn$ be a union-find state on…
- Kruskal.UF.find_defFind equals direct lookup. Let $\mathit{uf} \colon \mathrm{Fin}\,n \to \bbn$ be a union-find state on $n$ nodes, and let $i$ be one of its…
- Kruskal.totalWeight_nilTotal weight of the empty edge list. Over any number of vertices $n$, the total weight of the empty list of weighted edges is $0$; that…
- Kruskal.SymAdjGiven a list of weighted edges $\mathit{edges}$ on $n$ vertices, $\mathtt{SymAdj}\,\mathit{edges}\,u\,v$ holds when there exists an edge…
- TotalPreorderA total preorder: a preorder where
≤is total (complete). This is weaker thanLinearOrder— it does NOT require antisymmetry or… - LinearOrder.toTotalPreorderEvery
LinearOrderis aTotalPreorder.
- Used by 1
- Kruskal.kruskal_optimalOptimality of Kruskal's algorithm. Let $E$ be a list of weighted edges on $n$ vertices, and let $S$ be another such list in which every…
Lean source view module on GitHub
set_option relaxedAutoImplicit false in set_option autoImplicit false in lemma Kruskal.processEdges_optimal {n : ℕ} (edges : List (WEdge n)) (uf : UF n) (base : List (WEdge n)) (huf : ∀ a b : Fin n, uf a = uf b ↔ Reach base a b) (S : List (WEdge n)) (hSsub : ∀ e ∈ S, e ∈ edges) (hSspan : UF.SamePartition (uf.mergeAll S) (uf.mergeAll edges)) (hsorted : List.Pairwise (fun e1 e2 => e1.weight ≤ e2.weight) edges) : totalWeight (processEdges edges uf []) ≤ totalWeight S := by induction' edges with e edges ih generalizing uf base S · simp [processEdges, totalWeight] · by_cases he : uf.find e.u = uf.find e.v · obtain ⟨S', hS'sub, hS'span, hS'weight⟩ : ∃ S', (∀ e ∈ S', e ∈ edges) ∧ (uf.mergeAll S').SamePartition (uf.mergeAll edges) ∧ totalWeight S' ≤ totalWeight S := by apply reduce_to_rest · exact hSsub · convert hSspan.trans _ using 1 convert mergeAll_cons_eq uf e edges using 1 rw [merge_noop]; aesop · exact he rw [processEdges_skip he] exact le_trans (ih uf base huf S' hS'sub hS'span ((List.pairwise_cons.mp hsorted).2)) hS'weight · by_cases heS : e ∈ S <;> simp_all +decide [processEdges_take_weight] · have hS'_subset : UF.SamePartition ((uf.merge e.u e.v).mergeAll (S.erase e)) ((uf.merge e.u e.v).mergeAll edges) := by have hp1 : UF.SamePartition (uf.mergeAll (S.erase e ++ [e])) (uf.mergeAll (e :: edges)) := (mergeAll_perm uf (erase_append_perm heS).symm).trans hSspan have hp2 : UF.SamePartition ((uf.merge e.u e.v).mergeAll (S.erase e)) (uf.mergeAll (S.erase e ++ [e])) := (by convert mergeAll_perm uf (show List.Perm (S.erase e ++ [e]) (e :: S.erase e) from by grind) using 1 <;> try rfl : UF.SamePartition (uf.mergeAll (S.erase e ++ [e])) ((uf.merge e.u e.v).mergeAll (S.erase e))).symm convert hp2.trans ‹_› using 1 <;> try rfl obtain ⟨S', hS'_subset, hS'_span, hS'_weight⟩ := reduce_to_rest (uf.merge e.u e.v) e edges (S.erase e) (by grind) hS'_subset (by simp [UF.merge]) have := ih (uf.merge e.u e.v) (base ++ [e]) (by intros a b exact mergeAll_iff_reach uf base [e] huf a b) S' hS'_subset hS'_span linarith [totalWeight_erase S e heS, processEdges_take_weight (e := e) (rest := edges) (uf := uf) (fun h => he ((huf _ _).1 h))] · obtain ⟨f, hfS, hf⟩ : ∃ f ∈ S, UF.SamePartition ((uf.merge e.u e.v).mergeAll (S.erase f)) (uf.mergeAll S) := by apply uf_exchange · exact huf · exact (hSspan _ _).2 ((mergeAll_iff_reach uf base (e :: edges) huf _ _).2 (Relation.ReflTransGen.single (by exact ⟨e, by aesop⟩))) · exact fun h => he <| (huf _ _).1 h obtain ⟨S', hS'sub, hS'span, hS'weight⟩ : ∃ S' : List (WEdge n), (∀ x ∈ S', x ∈ edges) ∧ UF.SamePartition ((uf.merge e.u e.v).mergeAll S') ((uf.merge e.u e.v).mergeAll edges) ∧ totalWeight S' ≤ totalWeight (S.erase f) := by apply reduce_to_rest any_goals exact e · grind · refine hf.trans ?_; convert hSspan using 1 <;> try rfl · unfold UF.merge; aesop have := ih (uf.merge e.u e.v) (base ++ [e]) (mergeAll_iff_reach uf base [e] huf) S' hS'sub hS'span have hfedges : f ∈ edges := by rcases hSsub f hfS with rfl | h · exact absurd hfS heS · exact h linarith [totalWeight_erase S f hfS, hsorted.1 f hfedges, processEdges_take_weight (e := e) (rest := edges) (uf := uf) (fun h => he ((huf _ _).1 h))]