Every directed cut bounds an integral unit flow
ProvedDirKECC1549.Main.unit_flow_cut_bounddirected-graphsnetwork-flows
Let be a finite directed multigraph, the support of an integral unit-capacity – flow of value , and a vertex set containing and excluding . Then
The outgoing edges are counted with multiplicity. This is weak duality for the unit-capacity flow and directed cut encodings; loops are permitted.
Preamble
import Definitions.Def_DirKECC1549_Main_Alg3 set_option autoImplicit false
Formal statement
namespace DirKECC1549.Main
theorem unit_flow_cut_bound {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)
(S : Finset (Fin n)) (hS : IsCut S u v) : q ≤ outCount D S := 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.