Augmenting a unit flow along a residual walk
ProvedDirKECC1549.Main.unit_flow_residual_augmentdirected-graphsnetwork-flows
Let be a finite directed multigraph, let , and let support an integral unit-capacity – flow of value . Form the residual graph by reversing precisely the edges in . If is reachable from in that residual graph, then has an integral unit-capacity – flow of value .
This is the augmenting-path step of Ford–Fulkerson for unit-capacity edges. Distinct edge identifiers represent parallel edges, and loops are allowed.
Preamble
import Definitions.Def_DirKECC1549_Main_Alg3 set_option autoImplicit false
Formal statement
namespace DirKECC1549.Main
theorem unit_flow_residual_augment {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) (hr : Reach (flipEdges D F) u v) :
∃ F' : Finset (Fin m), IsUnitFlow D F' u v (q + 1) := by sorry
end DirKECC1549.Main
Source
Ford–Fulkerson, Flows in Networks (1962), Chapter I, Section 5, augmenting path method, p.19; also Georgiadis et al., STOC 2027 submission #1549, Section 2 p.9, for the mission graph encoding.