Extracting a trail from a positive integral unit flow
ProvedDirKECC1549.Main.unit_flow_extract_traildirected-graphsnetwork-flows
Let be a finite directed multigraph, let , and let be the support of an integral unit-capacity – flow of value . There is a directed – trail using only edges of such that deleting the edges of from leaves the support of a unit-capacity – flow of value .
This is the one-trail extraction step in the integral flow decomposition theorem. Parallel edges are distinguished by their identifiers, and loops are allowed.
Preamble
import Definitions.Def_DirKECC1549_Main_Alg3 set_option autoImplicit false
Formal statement
namespace DirKECC1549.Main
theorem unit_flow_extract_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 ∧
IsUnitFlow D (F \ p.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.