has_vertex_disjoint_paths
A graph Q and p terminal pairs (s_i, t_i) admit mutually vertex-disjoint paths if there exist paths P_i from s_i to t_i whose vertex sets are pairwise disjoint.
Statement
def has_vertex_disjoint_paths {V : Type*} (Q : SimpleGraph V) (p : ℕ) (s t : Fin p → V) : Prop
- Defined in
- arXiv:2611.06209, Section 4
- Verified
- 05 Nov 2026
- Axioms
- none listed
Read back from the Lean
Given a simple graph $Q$ on a vertex type $V$, a natural number $p$, and source and target maps $s, t : \mathrm{Fin}\ p \to V$, the proposition asserts that there exists a family of walks $P = (P(i))_{i : \mathrm{Fin}\ p}$ in $Q$, where each $P(i)$ is a walk from $s(i)$ to $t(i)$, such that: 1. For every $i : \mathrm{Fin}\ p$, $P(i)$ is a path (has no repeated vertices); and 2. For all $i, j : \mathrm{Fin}\ p$ with $i \neq j$, the vertex supports of $P(i)$ and $P(j)$ are disjoint (they share no vertices).
Written by a model that saw only the Lean, never the English above. If the two disagree, that is worth a challenge.
Lean source view module on GitHub
/-- Existence of mutually vertex-disjoint paths in graph Q connecting p terminal pairs. -/ def has_vertex_disjoint_paths {V : Type*} (Q : SimpleGraph V) (p : ℕ) (s t : Fin p → V) : Prop := ∃ P : (i : Fin p) → Q.Walk (s i) (t i), (∀ i, (P i).IsPath) ∧ ∀ i j, i ≠ j → (P i).support.Disjoint (P j).support