AFTD Auto-Formalizing Theoretical Domains

Kruskal.reduce_to_rest

theoremverifiedimported Lean

Dropping 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 endpoints $u$ and $v$, and let $\mathit{rest}$ and $S$ be lists of weighted edges. Suppose every edge of $S$ occurs in the list $e :: \mathit{rest}$ formed by prepending $e$ to $\mathit{rest}$; that merging all edges of $S$ into $\mathit{uf}$ induces the same partition of the nodes as merging all edges of $\mathit{rest}$ into $\mathit{uf}$; and that $e$ is already redundant for $\mathit{uf}$, meaning $\mathit{uf}(u) = \mathit{uf}(v)$. Then there exists a list $S'$ of weighted edges, every one of which occurs in $\mathit{rest}$, such that merging all edges of $S'$ into $\mathit{uf}$ induces the same partition as merging all edges of $\mathit{rest}$, and the total weight of $S'$ is at most the total weight of $S$.

Statement

set_option relaxedAutoImplicit false in
set_option autoImplicit false in
lemma Kruskal.reduce_to_rest {n : ℕ} (uf : UF n) (e : WEdge n) (rest S : List (WEdge n))
    (hSsub : ∀ x ∈ S, x ∈ e :: rest)
    (hSspan : UF.SamePartition (uf.mergeAll S) (uf.mergeAll rest))
    (hred : uf e.u = uf e.v) :
    ∃ S' : List (WEdge n),
      (∀ x ∈ S', x ∈ rest) ∧
      UF.SamePartition (uf.mergeAll S') (uf.mergeAll rest) ∧
      totalWeight S' ≤ totalWeight S
Source
TCSlib, `Kruskal.reduce_to_rest`
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.reduce_to_rest
--- TCSlib/GraphTheory/Kruskal/Exchange.lean:166 (Kruskal.reduce_to_rest)
+++ as compiled here
@@ -1,2 +1,4 @@
-lemma reduce_to_rest {n : ℕ} (uf : UF n) (e : WEdge n) (rest S : List (WEdge n))
+set_option relaxedAutoImplicit false in
+set_option autoImplicit false in
+lemma Kruskal.reduce_to_rest {n : ℕ} (uf : UF n) (e : WEdge n) (rest S : List (WEdge n))
     (hSsub : ∀ x ∈ S, x ∈ e :: rest)
@@ -18,3 +20,3 @@
       · convert ih (uf.merge x.u x.v) _ using 1
-        unfold UF.merge; aesop
+        all_goals first | rfl | (unfold UF.merge; simp [hred])
       · convert ih uf hred using 1
Verified
07 Oct 2026
Axioms
Classical.choiceQuot.soundpropext
Built on 11
  • 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.SamePartition.transTransitivity of the same-partition relation. Let $n$ be a natural number, and let…
  • 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.rflReflexivity of the same-partition relation. Fix $n \in \bbn$, and recall that a union-find state on $n$ nodes is a function…
  • 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.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.WEdgeA weighted edge over $n$ vertices is a structure with two endpoints $u, v : \mathrm{Fin}\,n$ and a natural-number weight…
  • 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.totalWeightThe total weight of an edge list is the sum of the weights of all its edges:…
  • 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…
Used by 1
  • Kruskal.processEdges_optimalOptimality of the greedy edge-selection sweep. Let $\mathit{edges}$ be a list of weighted edges on $n$ vertices, sorted in nondecreasing…

Lean source view module on GitHub

set_option relaxedAutoImplicit false inset_option autoImplicit false inlemma Kruskal.reduce_to_rest {n : ℕ} (uf : UF n) (e : WEdge n) (rest S : List (WEdge n))    (hSsub : ∀ x ∈ S, x ∈ e :: rest)    (hSspan : UF.SamePartition (uf.mergeAll S) (uf.mergeAll rest))    (hred : uf e.u = uf e.v) :    ∃ S' : List (WEdge n),      (∀ x ∈ S', x ∈ rest) ∧      UF.SamePartition (uf.mergeAll S') (uf.mergeAll rest) ∧      totalWeight S' ≤ totalWeight S := by  revert hSspan hSsub hred  have mergeAll_filter_redundant (uf : UF n) (S : List (WEdge n)) (e : WEdge n)      (rest : List (WEdge n))      (hSsub : ∀ x ∈ S, x ∈ e :: rest) (hred : uf e.u = uf e.v) :      UF.SamePartition (uf.mergeAll (S.filter (fun x => decide (x ∈ rest))))        (uf.mergeAll S) := by    induction' S with x S ih generalizing uf    · exact UF.SamePartition.rfl _    · by_cases hx : x ∈ rest <;> simp_all +decide      · convert ih (uf.merge x.u x.v) _ using 1        all_goals first | rfl | (unfold UF.merge; simp [hred])      · convert ih uf hred using 1        rw [show uf.mergeAll (e :: S) = (uf.merge e.u e.v).mergeAll S from by rfl]        rw [merge_noop _ _ _ hred]  intro hSsub hSspan hred  refine ⟨S.filter (fun x => decide (x ∈ rest)), ?_, ?_, ?_⟩  · intro x hx; simp at hx; exact hx.2  · exact (mergeAll_filter_redundant uf S e rest hSsub hred).trans hSspan  · unfold totalWeight    have hle : ∀ l : List (WEdge n),        (List.map WEdge.weight (l.filter (fun x => decide (x ∈ rest)))).sum ≤          (List.map WEdge.weight l).sum := by      intro l      induction l with      | nil => simp      | cons x l ih =>        by_cases hx : x ∈ rest <;> simp [hx] <;> linarith    exact hle S
See it in the graphDiscuss this resultChallenge it