Kruskal.mergeAll_iff_reach
Merging preserves the reachability invariant. Fix $n$ and let $uf : \mathrm{Fin}\,n \to \bbn$ be a union-find state assigning each of the $n$ nodes a representative. Let $\mathit{base}$ and $\mathit{edges}$ be lists of weighted edges on these $n$ vertices, and suppose $uf$ already encodes reachability along $\mathit{base}$, in the sense that for all nodes $a, b$ one has $uf(a) = uf(b)$ if and only if $a$ and $b$ are connected by a path through the edges of $\mathit{base}$. Then, writing $uf'$ for the state obtained by merging the endpoints of every edge of $\mathit{edges}$ into $uf$ in order, for all nodes $a, b$ one has $uf'(a) = uf'(b)$ if and only if $a$ and $b$ are connected by a path through the edges of the concatenated list $\mathit{base} \mathbin{+\!\!+} \mathit{edges}$.
Statement
set_option relaxedAutoImplicit false in set_option autoImplicit false in lemma Kruskal.mergeAll_iff_reach {n : ℕ} (uf : UF n) (base edges : List (WEdge n)) (huf : ∀ a b : Fin n, uf a = uf b ↔ Reach base a b) (a b : Fin n) : (uf.mergeAll edges) a = (uf.mergeAll edges) b ↔ Reach (base ++ edges) a b
- Source
- TCSlib, `Kruskal.mergeAll_iff_reach`
- 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_iff_reach← Kruskal.mergeAll_iff_reach (TCSlib/GraphTheory/Kruskal/UnionFind.lean:53): adapted
What was changed in
Kruskal.mergeAll_iff_reach--- TCSlib/GraphTheory/Kruskal/UnionFind.lean:53 (Kruskal.mergeAll_iff_reach) +++ as compiled here @@ -1,2 +1,4 @@ -lemma mergeAll_iff_reach {n : ℕ} (uf : UF n) (base edges : List (WEdge n)) +set_option relaxedAutoImplicit false in +set_option autoImplicit false in +lemma Kruskal.mergeAll_iff_reach {n : ℕ} (uf : UF n) (base edges : List (WEdge n)) (huf : ∀ a b : Fin n, uf a = uf b ↔ Reach base a b) (a b : Fin n) : @@ -4,4 +6,6 @@ induction' edges with e edges ih generalizing uf base - · convert huf a b using 1; simp +decide [Reach] + · convert huf a b using 1 <;> try rfl + simp +decide [Reach] · convert ih (uf.merge e.u e.v) (base ++ [e]) _ using 1 + · rfl · simp +decide [List.append_assoc] - Verified
- 16 Oct 2026
- Axioms
Classical.choiceQuot.soundpropext- Built on 10
- 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.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.Reach$\mathtt{Reach}\,\mathit{edges}$ is the reflexive--transitive closure of $\mathtt{SymAdj}\,\mathit{edges}$; that is,…
- Kruskal.reach_cons_iffHead–tail decomposition of reachability. Let $g$ be a weighted edge on $n$ vertices with endpoints $p$ and $q$, let $\mathit{rest}$ be a…
- 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…
- Used by 3
- Kruskal.uf_exchangeUnion-find form of the exchange argument. Let $\mathit{uf}\colon \mathrm{Fin}\,n \to \bbn$ be a union-find state whose classes coincide…
- Kruskal.processEdges_optimalOptimality of the greedy edge-selection sweep. Let $\mathit{edges}$ be a list of weighted edges on $n$ vertices, sorted in nondecreasing…
- Kruskal.mergeAll_init_iffCorrectness of union-find merging from the initial state. Fix a natural number $n$, and let $\mathit{edges}$ be a list of weighted edges…
Lean source view module on GitHub
set_option relaxedAutoImplicit false in set_option autoImplicit false in lemma Kruskal.mergeAll_iff_reach {n : ℕ} (uf : UF n) (base edges : List (WEdge n)) (huf : ∀ a b : Fin n, uf a = uf b ↔ Reach base a b) (a b : Fin n) : (uf.mergeAll edges) a = (uf.mergeAll edges) b ↔ Reach (base ++ edges) a b := by induction' edges with e edges ih generalizing uf base · convert huf a b using 1 <;> try rfl simp +decide [Reach] · convert ih (uf.merge e.u e.v) (base ++ [e]) _ using 1 · rfl · simp +decide [List.append_assoc] · intro a b; constructor <;> intro h <;> simp_all +decide [UF.merge] · split_ifs at h <;> simp_all +decide · have h_reach_base : Reach base a b := (‹Reach base a e.v›).trans (reach_symm ‹Reach base b e.v›) exact reach_mono h_reach_base fun x hx => by aesop · have h_reach : Reach (base ++ [e]) a e.v ∧ Reach (base ++ [e]) e.u b := ⟨reach_mono ‹_› fun x hx => List.mem_append_left _ hx, reach_mono ‹_› fun x hx => List.mem_append_left _ hx⟩ have h_ev_eu : Reach (base ++ [e]) e.v e.u := Relation.ReflTransGen.single ⟨e, by simp +decide, by simp +decide⟩ exact h_reach.1.trans (h_ev_eu.trans h_reach.2) · have h_au : Reach (base ++ [e]) a e.u := reach_mono h fun x hx => by aesop have h_euv : Reach (base ++ [e]) e.u e.v := Relation.ReflTransGen.single ⟨e, by aesop⟩ have h_vb : Reach (base ++ [e]) e.v b := reach_symm <| reach_mono ‹_› fun x hx => by aesop exact h_au.trans (h_euv.trans h_vb) · exact reach_mono h fun x hx => List.mem_append_left _ hx · have h_reach : Reach base a b ∨ (Reach base a e.u ∧ Reach base e.v b) ∨ (Reach base a e.v ∧ Reach base e.u b) := by convert reach_cons_iff.mp _ convert reach_mono h _ using 1 grind grind