Toggling a residual trail augments an integral unit flow
ProvedDirKECC1549.Main.unit_flow_toggle_residual_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 in the residual graph obtained by reversing the edges of . Then the symmetric difference
supports an integral unit-capacity – flow of value . The result also covers coincident endpoints: then both flow-balance equations have zero net source contribution. Parallel edges have distinct identifiers, and loops are allowed.
Preamble
import Definitions.Def_DirKECC1549_Main_Alg3 set_option autoImplicit false
Formal statement
namespace DirKECC1549.Main
theorem unit_flow_toggle_residual_trail {n m : ℕ} (D : Fin m → Fin n × Fin n)
(u v : Fin n) (q : ℕ) (F : Finset (Fin m))
(hF : IsUnitFlow D F u v q) (p : List (Fin m))
(hp : IsTrail (flipEdges D F) u p v) :
IsUnitFlow D ((F \ p.toFinset) ∪ (p.toFinset \ F)) u v (q + 1) := by sorry
end DirKECC1549.Main
Source
Ford–Fulkerson, Flows in Networks (1962), Chapter I, Section 5, augmentation along a residual path, p.19; generalized to residual trails for the mission unit-flow encoding, Georgiadis et al., STOC 2027 submission #1549, Section 2 p.9.