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
- vertex_disjoint_routing_exists_zeroWith
p = 0the disjoint-paths predicate holds, so it is not vacuously false.
- vertex_disjoint_routing_exists_zeroWith
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