Directed edge-Menger theorem: resilience implies disjoint trails
ProvedDirKECC1549.Main.edge_menger_sufficiencydirected-graphsedge-connectivitymengers-theorem
Let be a finite directed multigraph, vertices and . Suppose that for every set of fewer than edge identifiers there is an -to- directed walk avoiding . Then there are pairwise edge-disjoint directed trails from to .
This is the existence direction of the directed edge form of Menger’s theorem. Parallel edges have distinct identifiers, and loops are allowed. When , any number of empty trails suffices; when , the empty family suffices.
Preamble
import Definitions.Def_DirKECC1549_Main_Graph set_option autoImplicit false
Formal statement
namespace DirKECC1549.Main
theorem edge_menger_sufficiency {n m : ℕ} (D : Fin m → Fin n × Fin n) (k : ℕ)
(x y : Fin n) (h : ∀ F : Finset (Fin m), F.card < k →
∃ p, IsWalk D x p y ∧ ∀ e ∈ p, e ∉ F) : HasDisjointPaths D k x y := by sorry
end DirKECC1549.Main
Source
Directed edge-Menger theorem, EPFL Graph Theory lecture notes, Lecture 9, Section 1, https://www.epfl.ch/labs/disopt/wp-content/uploads/2019/11/GT19_notes_to_date.pdf ; also Georgiadis et al., STOC 2027 submission #1549, Section 2 p.9. This is the existence direction for the mission's multigraph and trail encoding.