AFTD Auto-Formalizing Theoretical Domains

Kruskal.mergeAll_iff_reach

theoremverifiedimported Lean

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