Positive integral unit flow contains a directed trail
ProvedDirKECC1549.Main.positive_flow_traildirected-graphsnetwork-flows
Let be a finite directed multigraph with distinct vertices , and let support an integral unit-capacity – flow of positive value. There is a directed – trail whose edge identifiers all lie in .
This path-existence fact is a step in integral flow decomposition. The graph may contain loops and parallel edges; a trail uses no edge identifier twice.
Preamble
import Definitions.Def_DirKECC1549_Main_Alg3 set_option autoImplicit false
Formal statement
namespace DirKECC1549.Main
theorem positive_flow_trail {n m : ℕ} (D : Fin m → Fin n × Fin n)
(u v : Fin n) (huv : u ≠ v) (q : ℕ) (F : Finset (Fin m))
(hF : IsUnitFlow D F u v (q + 1)) :
∃ p : List (Fin m), IsTrail D u p v ∧ p.toFinset ⊆ F := by sorry
end DirKECC1549.Main
Source
Derived reachability step in 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, for the mission graph encoding.