Adding a disjoint directed trail to a unit flow
ProvedDirKECC1549.Main.unit_flow_add_traildirected-graphsnetwork-flows
Let be a finite directed multigraph, let support an integral unit-capacity flow of value from to , and let be a directed – trail whose edge set is disjoint from . Then the union of with the edges of supports an integral unit-capacity – flow of value .
This conservation lemma constructs the flow of a disjoint family one trail at a time. Edge identifiers distinguish parallel edges, loops are allowed, and the statement includes coincident endpoints.
Preamble
import Definitions.Def_DirKECC1549_Main_Alg3 set_option autoImplicit false
Formal statement
namespace DirKECC1549.Main
theorem unit_flow_add_trail {n m : ℕ} (D : Fin m → Fin n × Fin n)
(u v : Fin n) (q : ℕ) (F : Finset (Fin m)) (p : List (Fin m))
(hF : IsUnitFlow D F u v q) (hp : IsTrail D u p v)
(hdis : Disjoint F p.toFinset) : IsUnitFlow D (F ∪ p.toFinset) u v (q + 1) := by sorry
end DirKECC1549.Main
Source
Derived conservation step for 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.