Kruskal.exchange_with_base
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.Kruskal.exchange_with_base← Kruskal.exchange_with_base (TCSlib/GraphTheory/Kruskal/Exchange.lean:63): verbatim
- 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
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.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