Unit-flow decomposition into edge-disjoint trails
ProvedDirKECC1549.Main.unit_flow_decompositiondirected-graphsnetwork-flows
Let be a finite directed multigraph with distinct vertices and let . There are pairwise edge-disjoint directed trails from to if and only if there is an integral unit-capacity – flow of value .
Flows are represented by the set of edges carrying one unit. Parallel edges have distinct identifiers and loops are allowed; any circulation components need not appear in the trails.
Preamble
import Definitions.Def_DirKECC1549_Main_Alg3 set_option autoImplicit false
Formal statement
namespace DirKECC1549.Main
theorem unit_flow_decomposition {n m : ℕ} (D : Fin m → Fin n × Fin n)
(u v : Fin n) (huv : u ≠ v) (q : ℕ) :
HasDisjointPaths D q u v ↔ ∃ F : Finset (Fin m), IsUnitFlow D F u v q := by sorry
end DirKECC1549.Main
Source
Flow decomposition theorem; Ahuja, Magnanti and Orlin, Network Flows (1993), Section 3.5; see also Georgiadis et al., STOC 2027 submission #1549, Section 2 p.9.