Kruskal.reduce_to_rest
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.Kruskal.reduce_to_rest← Kruskal.reduce_to_rest (TCSlib/GraphTheory/Kruskal/Exchange.lean:166): adapted
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
Choose a tactic — a marked line — to see the goals Lean had before and after it, as in Lean’s infoview. Step with ← → or j k.
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