AFTD Auto-Formalizing Theoretical Domains

Kruskal.processEdges_optimal

theoremverifiedimported Lean

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.
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 than LinearOrder — it does NOT require antisymmetry or…
  • LinearOrder.toTotalPreorderEvery LinearOrder is a TotalPreorder.
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))]
See it in the graphDiscuss this resultChallenge it