Directed edge-Menger theorem: cut lower bounds imply disjoint trails
ProvedDirKECC1549.Main.edge_menger_cutdirected-graphsedge-connectivitymengers-theorem
Let be a finite directed multigraph, vertices, and . Suppose that every vertex set containing and excluding has at least outgoing edges, counted with multiplicity. Then has pairwise edge-disjoint directed trails from to .
This is the cut-to-path direction of the directed edge form of Menger’s theorem. The graph may have loops and parallel edges, and the trails are lists without repeated edge identifiers.
Preamble
import Definitions.Def_DirKECC1549_Main_Graph set_option autoImplicit false
Formal statement
namespace DirKECC1549.Main
theorem edge_menger_cut {n m : ℕ} (D : Fin m → Fin n × Fin n) (k : ℕ)
(x y : Fin n) (hxy : x ≠ y)
(h : ∀ S : Finset (Fin n), x ∈ S → y ∉ S → k ≤ outCount D S) :
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. Cut-to-path direction for the mission's graph encoding.