Disjoint trail families form a unit-capacity flow
ProvedDirKECC1549.Main.trail_family_flowdirected-graphsnetwork-flows
Let be a finite directed multigraph, let be vertices, and let be pairwise edge-disjoint directed – trails. The union of their edge sets is the support of an integral unit-capacity – flow of value .
The assertion includes , coincident endpoints, parallel edges and loops. It provides the conservation identity for constructing a unit flow from a family of trails.
Preamble
import Definitions.Def_DirKECC1549_Main_Alg3 set_option autoImplicit false
Formal statement
namespace DirKECC1549.Main
theorem trail_family_flow {n m : ℕ} (D : Fin m → Fin n × Fin n)
(u v : Fin n) (q : ℕ) (P : Fin q → List (Fin m))
(hP : ∀ i, IsTrail D u (P i) v)
(hd : ∀ i j, i ≠ j → Disjoint (P i).toFinset (P j).toFinset) :
IsUnitFlow D (Finset.univ.biUnion (fun i ↦ (P i).toFinset)) u v q := by sorry
end DirKECC1549.Main
Source
Derived elementary step of integral flow decomposition, Ahuja, Magnanti and Orlin, Network Flows (1993), Section 3.5; also Georgiadis et al., STOC 2027 submission #1549, Section 2 p.9, in the mission multigraph encoding.