MaxFlowMinCutTheorem

The Max-Flow Min-Cut Theorem is a fundamental result in network flow theory. In a directed graph G=(V,E) with a designated source s and sink t, each edge e has a nonnegative capacity c(e). A flow f assigns to each edge a real value f(e) with 0 ≤ f(e) ≤ c(e), satisfies conservation at all vertices except s and t, and has a value defined as the net flow out of s (equivalently into t). The theorem states that the maximum possible flow from s to t equals the minimum total capacity of any s-t cut.

An s-t cut is a partition of V into S and T with s ∈ S and t ∈ T; its capacity is the sum of capacities of edges from S to T. Intuitively, a cut measures how much flow would be blocked if all edges from S to T were removed. The theorem asserts no matter how the flow is arranged, the maximum flow value cannot exceed the capacity of any s-t cut, and there exists a flow whose value equals the capacity of some minimum cut.

A standard route to proving the theorem uses the residual graph of a flow, where residual capacities reflect how much more flow can be sent along edges or pushed back. When no augmenting path from s to t exists in the residual graph, the set of vertices reachable from s defines an S; the edges leaving S form a cut whose capacity equals the current flow value, hence is minimum. The theorem also implies strong duality between the max-flow and min-cut problems.

Consequences include the existence of integral max flows when all capacities are integers, and various polynomial-time algorithms for computing max flow, such as Ford-Fulkerson, Edmonds-Karp, and Dinic’s algorithm. The theorem provides a unifying perspective linking feasibility of flows with bottlenecks in networks.