Integral unit-capacity max-flow min-cut theorem
ProvedDirKECC1549.Main.unit_flow_min_cutdirected-graphsnetwork-flows
Let be a finite directed multigraph with distinct vertices . There is a natural number which is both the largest value of an integral unit-capacity – flow and the minimum number of outgoing edges of a vertex set containing but excluding .
Flow values and cut sizes count parallel edges separately. Loops are allowed, and a flow is represented by its set of edges carrying one unit.
Preamble
import Definitions.Def_DirKECC1549_Main_Alg3 set_option autoImplicit false
Formal statement
namespace DirKECC1549.Main
theorem unit_flow_min_cut {n m : ℕ} (D : Fin m → Fin n × Fin n)
(u v : Fin n) (huv : u ≠ v) :
∃ q : ℕ, IsGreatest {q : ℕ | ∃ F : Finset (Fin m), IsUnitFlow D F u v q} q ∧
IsLeast ((fun S ↦ outCount D S) '' {S : Finset (Fin n) | IsCut S u v}) q := by sorry
end DirKECC1549.Main
Source
Ford–Fulkerson max-flow min-cut theorem with integral unit capacities; Ford and Fulkerson, Flows in Networks (1962), Chapter I, Theorem 5.1, p.19 and integrality theorem; see also Georgiadis et al., STOC 2027 submission #1549, Section 2 p.9.