AFTD Auto-Formalizing Theoretical Domains

Kruskal.mergeAll_init_iff

theoremverifiedimported Lean

Correctness of union-find merging from the initial state. Fix a natural number $n$, and let $\mathit{edges}$ be a list of weighted edges on the vertex set $\mathrm{Fin}\,n$. Consider the union-find state obtained by starting from the initial state on $n$ nodes, in which every node is its own representative, and processing $\mathit{edges}$ in order, so that at each weighted edge the components of the two endpoints of that edge are merged. Then, for any two vertices $a, b \in \mathrm{Fin}\,n$, the vertices $a$ and $b$ carry the same representative in the resulting state if and only if $a$ and $b$ are connected by a path through the edges of $\mathit{edges}$ — equivalently, if and only if the reflexive--transitive closure of symmetric adjacency along $\mathit{edges}$ relates $a$ to $b$.

Statement

set_option relaxedAutoImplicit false in
set_option autoImplicit false in
lemma Kruskal.mergeAll_init_iff {n : ℕ} (edges : List (WEdge n)) (a b : Fin n) :
    (UF.init n).mergeAll edges a = (UF.init n).mergeAll edges b ↔ Reach edges a b
Source
TCSlib, `Kruskal.mergeAll_init_iff`
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.mergeAll_init_iff
--- TCSlib/GraphTheory/Kruskal/UnionFind.lean:86 (Kruskal.mergeAll_init_iff)
+++ as compiled here
@@ -1,4 +1,7 @@
-lemma mergeAll_init_iff {n : ℕ} (edges : List (WEdge n)) (a b : Fin n) :
+set_option relaxedAutoImplicit false in
+set_option autoImplicit false in
+lemma Kruskal.mergeAll_init_iff {n : ℕ} (edges : List (WEdge n)) (a b : Fin n) :
     (UF.init n).mergeAll edges a = (UF.init n).mergeAll edges b ↔ Reach edges a b := by
   convert mergeAll_iff_reach (UF.init n) [] edges _ a b
+  · rfl
   intro a b; constructor <;> intro h <;> simp_all +decide [Reach]
Verified
16 Oct 2026
Axioms
Classical.choiceQuot.soundpropext
Built on 8
  • 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.UF.init$\mathtt{init}\,n$ constructs the identity union-find on $n$ nodes: every node $i$ is its own representative, i.e.\…
  • 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.Reach$\mathtt{Reach}\,\mathit{edges}$ is the reflexive--transitive closure of $\mathtt{SymAdj}\,\mathit{edges}$; that is,…
  • 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.init_findFind on the initial union-find. Consider the identity union-find on $n$ nodes, in which every node is its own representative. For every…
  • 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…
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.mergeAll_init_iff {n : ℕ} (edges : List (WEdge n)) (a b : Fin n) :
    (UF.init n).mergeAll edges a = (UF.init n).mergeAll edges b ↔ Reach edges a b := by
  convert mergeAll_iff_reach (UF.init n) [] edges _ a b
  · rfl
  intro a b; constructor <;> intro h <;> simp_all +decide [Reach]
  · cases a; cases b; aesop
  · induction h <;> simp_all +decide [SymAdj]
See it in the graphDiscuss this resultChallenge it