Integral unit flow: augment or exhibit an equal cut
ProvedDirKECC1549.Main.unit_flow_augment_or_cutdirected-graphsnetwork-flows
Let be a finite directed multigraph with distinct vertices , and let be the support of an integral unit-capacity – flow of value . Then either there is an integral unit-capacity – flow of value , or there is a vertex set with , , and exactly outgoing edges.
This is the augmentation-or-cut alternative underlying the Ford–Fulkerson proof. Edge identifiers distinguish 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_augment_or_cut {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) :
(∃ F' : Finset (Fin m), IsUnitFlow D F' u v (q + 1)) ∨
∃ S : Finset (Fin n), IsCut S u v ∧ outCount D S = q := by sorry
end DirKECC1549.Main
Source
Derived step in Ford–Fulkerson, Flows in Networks (1962), Chapter I, Section 5, Theorem 5.1 p.19, for the mission’s integral unit-flow encoding; see also Georgiadis et al., STOC 2027 submission #1549, Section 2 p.9.