AFTD Auto-Formalizing Theoretical Domains

Kruskal.exchange_with_base

theoremverifiedimported Lean

Base-relative exchange of an edge in Kruskal's algorithm. Let $\mathit{base}$ and $S$ be lists of weighted edges on $n$ vertices, and let $e$ be a weighted edge whose two endpoints are distinct. Suppose the endpoints of $e$ are connected by a path using the edges of $\mathit{base}$ together with those of $S$, but are not connected using the edges of $\mathit{base}$ alone. Then there is an edge $f$ occurring in $S$ such that, for every pair of vertices $a$ and $b$ connected by a path through the edges of $\mathit{base}$ together with $S$, the vertices $a$ and $b$ are still connected by a path through the edges of $\mathit{base}$ together with the edges of $S$ after removing one occurrence of $f$ and adjoining $e$.

Statement

set_option relaxedAutoImplicit false in
set_option autoImplicit false in
lemma Kruskal.exchange_with_base {n : ℕ} {base S : List (WEdge n)} {e : WEdge n}
    (hreach : Reach (base ++ S) e.u e.v)
    (hbase : ¬Reach base e.u e.v) (hne : e.u ≠ e.v) :
    ∃ f ∈ S, ∀ a b, Reach (base ++ S) a b →
      Reach (base ++ S.erase f ++ [e]) a b
Source
TCSlib, `Kruskal.exchange_with_base`
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 11
  • Kruskal.exchange_take_headHead-edge exchange preserves reachability. Let $\mathit{base}$ and $\mathit{rest}$ be lists of weighted edges on $n$ vertices, and let $g$…
  • Kruskal.reach_mem_iffReachability depends only on the edge set. Fix $n \in \bbn$, and let $l_1$ and $l_2$ be two lists of weighted edges on the vertex set…
  • 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_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_of_memEndpoints of a listed edge are reachable. Let $\mathit{edges}$ be a list of weighted edges on $n$ vertices, and let $e$ be a weighted edge…
  • 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.WEdgeA weighted edge over $n$ vertices is a structure with two endpoints $u, v : \mathrm{Fin}\,n$ and a natural-number weight…
  • Kruskal.exchange_take_head'Edge exchange preserving reachability, reversed orientation. Fix $n$ and consider weighted edges on a vertex set of size $n$, each edge…
  • Kruskal.reach_liftLifting reachability along an edge set. Let $\mathit{edges}$ and $\mathit{edges}'$ be two lists of weighted edges on $n$ vertices, and…
  • 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…
Used by 1
  • 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…

Lean source view module on GitHub

set_option relaxedAutoImplicit false inset_option autoImplicit false inlemma Kruskal.exchange_with_base {n : ℕ} {base S : List (WEdge n)} {e : WEdge n}    (hreach : Reach (base ++ S) e.u e.v)    (hbase : ¬Reach base e.u e.v) (hne : e.u ≠ e.v) :    ∃ f ∈ S, ∀ a b, Reach (base ++ S) a b →      Reach (base ++ S.erase f ++ [e]) a b := by  revert e  intro e hreach hbase hne  induction' S with g S ih generalizing base  · aesop  · by_cases hcase1 : Reach (base ++ S) e.u e.v    · specialize ih hcase1 hbase      obtain ⟨f, hf1, hf2⟩ := ih      simp_all +decide [List.erase_cons]      refine Or.inr ⟨f, hf1, fun a b hab => ?_⟩      split_ifs <;> simp_all +decide      · apply reach_lift        rotate_right        exact base ++ f :: S        · intro a b hab          exact reach_mono (by tauto) (by aesop)        · assumption      · have h_reach : Reach (base ++ S) a b ∨            (Reach (base ++ S) a g.u ∧ Reach (base ++ S) g.v b) ∨            (Reach (base ++ S) a g.v ∧ Reach (base ++ S) g.u b) := by          have h_iff : Reach (base ++ g :: S) a b ↔ Reach (base ++ S) a b ∨              (Reach (base ++ S) a g.u ∧ Reach (base ++ S) g.v b) ∨              (Reach (base ++ S) a g.v ∧ Reach (base ++ S) g.u b) := by            convert reach_cons_iff using 1            convert reach_mem_iff _ using 1            grind          exact h_iff.mp hab        rcases h_reach with h | h | h        · exact reach_mono (hf2 a b h) fun x hx => by aesop        · have h1 : Reach (base ++ g :: (S.erase f ++ [e])) a g.u :=            reach_mono (hf2 _ _ h.1) fun x hx => by aesop          have h2 : Reach (base ++ g :: (S.erase f ++ [e])) g.v b :=            reach_mono (hf2 _ _ h.2) fun x hx => by aesop          have hg : Reach (base ++ g :: (S.erase f ++ [e])) g.u g.v :=            Relation.ReflTransGen.single ⟨g, by aesop⟩          exact h1.trans (hg.trans h2)        · have h1 : Reach (base ++ g :: (S.erase f ++ [e])) a g.v :=            reach_mono (hf2 _ _ h.1) fun x hx => by aesop          have h2 : Reach (base ++ g :: (S.erase f ++ [e])) g.u b :=            reach_mono (hf2 _ _ h.2) fun x hx => by aesop          have hg : Reach (base ++ g :: (S.erase f ++ [e])) g.v g.u :=            reach_symm (reach_of_mem (by simp +decide :              g ∈ base ++ g :: (S.erase f ++ [e])))          exact h1.trans (hg.trans h2)    · have hswap : Reach (base ++ S) e.u g.u ∧ Reach (base ++ S) g.v e.v ∨          Reach (base ++ S) e.u g.v ∧ Reach (base ++ S) g.u e.v := by        have hreach_g : Reach (g :: (base ++ S)) e.u e.v :=          (reach_mem_iff (by grind)).1 hreach        cases reach_cons_iff.mp hreach_g <;> aesop      cases' hswap with hswap hswap      · have hlift : ∀ a b, Reach (base ++ g :: S) a b → Reach (base ++ S ++ [e]) a b :=          exchange_take_head hswap.left hswap.right        aesop      · have hlift : ∀ a b, Reach (base ++ g :: S) a b → Reach (base ++ S ++ [e]) a b :=          exchange_take_head' hswap.1 hswap.2        use g; simp        simpa only [List.append_assoc] using hlift
See it in the graphDiscuss this resultChallenge it