Transitivity of directed edge-disjoint path existence
ProvedDirKECC1549.Main.disjoint_paths_transdirected-graphsedge-connectivity
Let be a finite directed multigraph, vertices, and . If there are pairwise edge-disjoint directed trails from to and pairwise edge-disjoint directed trails from to , then there are pairwise edge-disjoint directed trails from to .
This directional transitivity is a consequence of the directed edge form of Menger's theorem and supports the equivalence of mutual -edge-connectivity. Loops and parallel edges are permitted, and vertices need not be distinct.
Preamble
import Definitions.Def_DirKECC1549_Main_Graph set_option autoImplicit false
Formal statement
namespace DirKECC1549.Main
theorem disjoint_paths_trans {n m : ℕ} (D : Fin m → Fin n × Fin n) (k : ℕ)
(x y z : Fin n) (hxy : HasDisjointPaths D k x y) (hyz : HasDisjointPaths D k y z) :
HasDisjointPaths D k x z := by sorry
end DirKECC1549.Main
Source
Derived consequence of directed edge-Menger theorem; Georgiadis et al., STOC 2027 submission #1549, Section 2 p.9 (edge connectivity and equivalence). See also https://www.epfl.ch/labs/disopt/wp-content/uploads/2019/11/GT19_notes_to_date.pdf, Lecture 9, Menger's theorem.