AFTD Auto-Formalizing Theoretical Domains

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.
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

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