AFTD Auto-Formalizing Theoretical Domains

vertex_disjoint_routing_exists

def

DisjointPathsExist: there is a tuple of paths in Q, the i-th joining s_i to t_i, whose supports are pairwise disjoint.

Statement

def vertex_disjoint_routing_exists {V : Type*} (Q : SimpleGraph V) {p : ℕ} (s t : Fin p → V) : Prop
Source
step towards weighted_spanning_tree_congestion_hardness_gap
Verified
05 Nov 2026
Axioms
none listed
Used by 1

Lean source view module on GitHub

/-- The disjoint-paths predicate: the `s_i`--`t_i` pairs can be joined by pairwise vertex-disjoint paths in `Q`. -/
def vertex_disjoint_routing_exists {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