Kruskal.mergeAll_congr
theoremverifiedimported Lean
Merging edges preserves equal partitions. Let $\mathit{uf}_1, \mathit{uf}_2 : \mathrm{Fin}\,n \to \bbn$ be two union-find states over $n$ nodes that induce the same partition, meaning that for all nodes $i, j$ one has $\mathit{uf}_1(i) = \mathit{uf}_1(j)$ if and only if $\mathit{uf}_2(i) = \mathit{uf}_2(j)$. Then for any list of weighted edges, folding that list into each state by successively merging the endpoints of every edge yields two states that again induce the same partition.
Statement
set_option relaxedAutoImplicit false in set_option autoImplicit false in lemma Kruskal.mergeAll_congr {n : ℕ} {uf1 uf2 : UF n} (edges : List (WEdge n)) (h : UF.SamePartition uf1 uf2) : UF.SamePartition (uf1.mergeAll edges) (uf2.mergeAll edges)
- Source
- TCSlib, `Kruskal.mergeAll_congr`
- 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_congr← Kruskal.mergeAll_congr (TCSlib/GraphTheory/Kruskal/UnionFind.lean:93): verbatim
- Verified
- 07 Oct 2026
- Axioms
Classical.choiceQuot.soundpropext- Built on 6
- 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.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.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.mergeAll_permPermutation invariance of edge merging. Fix $n$ and an initial union-find state $\mathit{uf} : \mathrm{Fin}\,n \to \bbn$. If two lists of…
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.mergeAll_congr {n : ℕ} {uf1 uf2 : UF n} (edges : List (WEdge n)) (h : UF.SamePartition uf1 uf2) : UF.SamePartition (uf1.mergeAll edges) (uf2.mergeAll edges) := by unfold UF.SamePartition at h ⊢ induction edges generalizing uf1 uf2 with | nil => exact h | cons e edges ih => refine ih (uf1 := uf1.merge e.u e.v) (uf2 := uf2.merge e.u e.v) ?_ intro i j; unfold UF.merge; grind