AFTD Auto-Formalizing Theoretical Domains

has_vertex_disjoint_paths

def

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