AFTD Auto-Formalizing Theoretical Domains

Kruskal.uf_exchange

theoremverifiedimported Lean

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.
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⟩
See it in the graphDiscuss this resultChallenge it