Kruskal.reach_cons_iff
Head–tail decomposition of reachability. Let $g$ be a weighted edge on $n$ vertices with endpoints $p$ and $q$, let $\mathit{rest}$ be a list of weighted edges on the same $n$ vertices, and let $a$ and $b$ be vertices; say two vertices are $\mathit{rest}$-connected when they are joined by a path using only the edges in $\mathit{rest}$. Then $a$ and $b$ are joined by a path through the edges of the list obtained by prepending $g$ to $\mathit{rest}$ if and only if at least one of the following holds: $a$ and $b$ are $\mathit{rest}$-connected; or $a$ is $\mathit{rest}$-connected to $p$ while $q$ is $\mathit{rest}$-connected to $b$; or $a$ is $\mathit{rest}$-connected to $q$ while $p$ is $\mathit{rest}$-connected to $b$.
Statement
set_option relaxedAutoImplicit false in set_option autoImplicit false in lemma Kruskal.reach_cons_iff {n : ℕ} {g : WEdge n} {rest : List (WEdge n)} {a b : Fin n} : Reach (g :: rest) a b ↔ Reach rest a b ∨ (Reach rest a g.u ∧ Reach rest g.v b) ∨ (Reach rest a g.v ∧ Reach rest g.u b)
- Source
- TCSlib, `Kruskal.reach_cons_iff`
- Lean proof
- By [Your Name], [Partner's Name (if applicable)], from github.com/Shilun-Allan-Li/tcslib at
c8a02591b1e5(Copyright (c) 2026 [Your Name] and [Partner's Name (if applicable)]. 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.reach_cons_iff← Kruskal.reach_cons_iff (TCSlib/GraphTheory/Kruskal/Reach.lean:76): verbatim
- Verified
- 07 Oct 2026
- Axioms
Classical.choiceQuot.soundpropext- Built on 6
- 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_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.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 2
- Kruskal.exchange_with_baseBase-relative exchange of an edge in Kruskal's algorithm. Let $\mathit{base}$ and $S$ be lists of weighted edges on $n$ vertices, and let…
- Kruskal.mergeAll_iff_reachMerging preserves the reachability invariant. Fix $n$ and let $uf : \mathrm{Fin}\,n \to \bbn$ be a union-find state assigning each of the…
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.reach_cons_iff {n : ℕ} {g : WEdge n} {rest : List (WEdge n)} {a b : Fin n} : Reach (g :: rest) a b ↔ Reach rest a b ∨ (Reach rest a g.u ∧ Reach rest g.v b) ∨ (Reach rest a g.v ∧ Reach rest g.u b) := by have mono : ∀ {x y}, Reach rest x y → Reach (g :: rest) x y := fun h => reach_mono h fun _ => List.mem_cons_of_mem _ have gadj : Reach (g :: rest) g.u g.v := Relation.ReflTransGen.single ⟨g, List.mem_cons_self .., Or.inl ⟨rfl, rfl⟩⟩ refine ⟨fun h => ?_, ?_⟩ · induction' h with c d hcd ih · exact Or.inl .refl · rcases ih with ⟨e, he, he'⟩ rcases he' with ⟨rfl, rfl⟩ | ⟨rfl, rfl⟩ <;> simp_all +decide [Reach] · rcases he with rfl | he · aesop · rename_i h rcases h with h | h | h · exact Or.inl <| h.tail ⟨e, he, by tauto⟩ · exact Or.inr <| Or.inl ⟨h.1, h.2.tail ⟨e, he, by tauto⟩⟩ · exact Or.inr <| Or.inr ⟨h.1, h.2.tail ⟨e, he, by tauto⟩⟩ · -- Backward edge: c = e.v, b = e.u. Use the IH for e.v, then reverse via e. rename_i h rcases he with rfl | he · -- e = g: IH is about g.v, goal is about g.u rcases h with h | ⟨h1, _⟩ | ⟨h1, _⟩ · exact Or.inr (Or.inr ⟨h, .refl⟩) · exact Or.inl h1 · exact Or.inr (Or.inr ⟨h1, .refl⟩) · -- e ∈ rest: Reach rest e.v e.u by symmetry, then chain have hrev := reach_symm (reach_of_mem he) rcases h with h | ⟨h1, h2⟩ | ⟨h1, h2⟩ · exact Or.inl (h.trans hrev) · exact Or.inr (Or.inl ⟨h1, h2.trans hrev⟩) · exact Or.inr (Or.inr ⟨h1, h2.trans hrev⟩) · rintro (h | ⟨h1, h2⟩ | ⟨h1, h2⟩) · exact mono h · exact (mono h1).trans (gadj.trans (mono h2)) · exact (mono h1).trans ((reach_symm gadj).trans (mono h2))