Kruskal.uf_exchange
Union-find form of the exchange argument. Let $\mathit{uf}\colon \mathrm{Fin}\,n \to \bbn$ be a union-find state whose classes coincide with the reachability classes of an edge list $\mathit{base}$: for all nodes $a,b$ one has $\mathit{uf}(a) = \mathit{uf}(b)$ if and only if $a$ and $b$ are joined by a path through the edges of $\mathit{base}$. Let $S$ be a further list of weighted edges, and let $e$ be a weighted edge with endpoints $u$ and $v$ such that merging every edge of $S$ into $\mathit{uf}$ places $u$ and $v$ in a common component, while $\mathit{uf}$ itself keeps them in distinct components. Then there is an edge $f \in S$ for which the state obtained by first merging $u$ with $v$ and then merging all edges of $S$ other than $f$ induces the same partition of the nodes as the state obtained by merging all edges of $S$ into $\mathit{uf}$.
Statement
set_option relaxedAutoImplicit false in set_option autoImplicit false in lemma Kruskal.uf_exchange {n : ℕ} (uf : UF n) (base S : List (WEdge n)) (e : WEdge n) (huf : ∀ a b : Fin n, uf a = uf b ↔ Reach base a b) (hconn : (uf.mergeAll S) e.u = (uf.mergeAll S) e.v) (hdiff : uf e.u ≠ uf e.v) : ∃ f ∈ S, UF.SamePartition ((uf.merge e.u e.v).mergeAll (S.erase f)) (uf.mergeAll S)
- Source
- TCSlib, `Kruskal.uf_exchange`
- 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.uf_exchange← Kruskal.uf_exchange (TCSlib/GraphTheory/Kruskal/Exchange.lean:125): adapted
What was changed in
Kruskal.uf_exchange--- TCSlib/GraphTheory/Kruskal/Exchange.lean:125 (Kruskal.uf_exchange) +++ as compiled here @@ -1,2 +1,4 @@ -lemma uf_exchange {n : ℕ} (uf : UF n) (base S : List (WEdge n)) (e : WEdge n) +set_option relaxedAutoImplicit false in +set_option autoImplicit false in +lemma Kruskal.uf_exchange {n : ℕ} (uf : UF n) (base S : List (WEdge n)) (e : WEdge n) (huf : ∀ a b : Fin n, uf a = uf b ↔ Reach base a b) @@ -36,3 +38,3 @@ apply mergeAll_iff_reach - convert mergeAll_iff_reach uf base [e] huf using 1 + exact mergeAll_iff_reach uf base [e] huf simp_all +decide [List.append_assoc] - Verified
- 16 Oct 2026
- Axioms
Classical.choiceQuot.soundpropext- Built on 15
- 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.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.exchange_with_baseBase-relative exchange of an edge in Kruskal's algorithm. Let $\mathit{base}$ and $S$ be lists of weighted edges on $n$ vertices, and let…
- Kruskal.Reach$\mathtt{Reach}\,\mathit{edges}$ is the reflexive--transitive closure of $\mathtt{SymAdj}\,\mathit{edges}$; that is,…
- Kruskal.reach_liftLifting reachability along an edge set. Let $\mathit{edges}$ and $\mathit{edges}'$ be two lists of weighted edges on $n$ vertices, and…
- Kruskal.reach_mem_iffReachability depends only on the edge set. Fix $n \in \bbn$, and let $l_1$ and $l_2$ be two lists of weighted edges on the vertex set…
- Kruskal.reach_monoMonotonicity of reachability under edge addition. Fix $n$, let $e_1$ and $e_2$ be lists of weighted edges on the vertex set…
- Kruskal.reach_symmSymmetry of reachability. Let $\mathit{edges}$ be a list of weighted edges on $n$ vertices, and call two vertices reachable when they are…
- 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.SymAdjGiven a list of weighted edges $\mathit{edges}$ on $n$ vertices, $\mathtt{SymAdj}\,\mathit{edges}\,u\,v$ holds when there exists an 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…
- 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 in set_option autoImplicit false in lemma Kruskal.uf_exchange {n : ℕ} (uf : UF n) (base S : List (WEdge n)) (e : WEdge n) (huf : ∀ a b : Fin n, uf a = uf b ↔ Reach base a b) (hconn : (uf.mergeAll S) e.u = (uf.mergeAll S) e.v) (hdiff : uf e.u ≠ uf e.v) : ∃ f ∈ S, UF.SamePartition ((uf.merge e.u e.v).mergeAll (S.erase f)) (uf.mergeAll S) := by obtain ⟨f, hfS, hswap⟩ : ∃ f ∈ S, ∀ a b, Reach (base ++ S) a b → Reach (base ++ S.erase f ++ [e]) a b := by apply exchange_with_base · exact (mergeAll_iff_reach uf base S huf e.u e.v).mp hconn · exact fun h => hdiff <| (huf _ _).2 h · contrapose! hdiff; aesop have hswap_symm : ∀ a b, Reach (base ++ S.erase f ++ [e]) a b → Reach (base ++ S) a b := by intro a b hab apply reach_lift (edges := base ++ S.erase f ++ [e]) _ hab intro a b ⟨g, hg, hg'⟩ rcases List.mem_append.mp hg with hg1 | hg1 · rcases List.mem_append.mp hg1 with hg2 | hg2 · exact reach_mono (.single ⟨g, hg2, hg'⟩) (fun x hx => List.mem_append_left _ hx) · exact reach_mono (.single ⟨g, List.mem_of_mem_erase hg2, hg'⟩) (fun x hx => List.mem_append_right _ hx) · have hge : e = g := (List.mem_singleton.mp hg1).symm subst hge have hreach_e : Reach (base ++ S) e.u e.v := (mergeAll_iff_reach uf base S huf e.u e.v).mp hconn rcases hg' with ⟨rfl, rfl⟩ | ⟨rfl, rfl⟩ · exact hreach_e · exact reach_symm hreach_e have hcomp_S : ∀ a b, (uf.mergeAll S) a = (uf.mergeAll S) b ↔ Reach (base ++ S) a b := mergeAll_iff_reach uf base S huf have hcomp_S' : ∀ a b, ((uf.merge e.u e.v).mergeAll (S.erase f)) a = ((uf.merge e.u e.v).mergeAll (S.erase f)) b ↔ Reach (base ++ S.erase f ++ [e]) a b := by have hcomp_e : ∀ a b, ((uf.merge e.u e.v).mergeAll (S.erase f)) a = ((uf.merge e.u e.v).mergeAll (S.erase f)) b ↔ Reach (base ++ [e] ++ S.erase f) a b := by apply mergeAll_iff_reach exact mergeAll_iff_reach uf base [e] huf simp_all +decide [List.append_assoc] apply reach_mem_iff; grind exact ⟨f, hfS, fun a b => by aesop⟩