AFTD Auto-Formalizing Theoretical Domains

Kruskal.reach_cons_iff

theoremverifiedimported Lean

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.
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

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