Kruskal.mergeAll_init_iff
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.Kruskal.mergeAll_init_iff← Kruskal.mergeAll_init_iff (TCSlib/GraphTheory/Kruskal/UnionFind.lean:86): adapted
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]