Max-flow min-cut theorem

A flow network is a directed graph (G=(V,E)) equipped with a nonnegative capacity (c(e)) for every edge (e), together with a distinguished source vertex (s) and sink vertex (t). The max-flow min-cut theorem states that the greatest value attainable by an (s)-(t) flow equals the smallest capacity of an (s)-(t) cut. It is a central result in combinatorial optimization, since it equates a global transportation problem with a separating certificate that can be verified locally.

The theorem also provides the principal structural explanation for several results concerning network optimization, disjoint paths, bipartite matching, and linear programming duality. Its algorithmic proof identifies either an additional route through which flow can be transmitted or a cut demonstrating that no larger flow is possible.

Mathematical formulation

For each directed edge ((u,v)\in E), a flow assigns a quantity (f(u,v)) satisfying the capacity constraint

[ 0\leq f(u,v)\leq c(u,v). ]

At every vertex other than (s) and (t), the total incoming flow equals the total outgoing flow:

[ \sum_{(u,v)\in E} f(u,v)

\sum_{(v,w)\in E} f(v,w). ]

This equation is the flow conservation condition. The value of the flow is the net amount leaving the source,

[ |f|

\sum_{(s,v)\in E} f(s,v)

\sum_{(v,s)\in E} f(v,s), ]

which, by conservation, is also the net amount entering the sink.

An (s)-(t) cut is a partition ((S,T)) of (V) such that (s\in S) and (t\in T). Its capacity is the sum of the capacities of all directed edges crossing from (S) to (T):

[ c(S,T)

\sum_{\substack{(u,v)\in E\u\in S,\ v\in T}} c(u,v). ]

Edges directed from (T) to (S) do not contribute to the cut capacity, although their carried flow affects the net flow crossing the partition.

The theorem can therefore be written as

[ \max_f |f|

\min_{\substack{S\subseteq V\s\in S,\ t\notin S}} c(S,V\setminus S). ]

The left-hand optimization ranges over all feasible flows, while the right-hand optimization ranges over all cuts separating the source from the sink.

Weak duality

Every feasible flow has value no greater than the capacity of any (s)-(t) cut. For a cut ((S,T)), conservation at vertices within (S\setminus{s}) causes all internal contributions to cancel, leaving

[ |f|

\sum_{\substack{(u,v)\in E\u\in S,\ v\in T}} f(u,v)

\sum_{\substack{(u,v)\in E\u\in T,\ v\in S}} f(u,v). ]

Because the second sum is nonnegative, its subtraction cannot increase the expression. Applying the capacity constraint to the first sum gives

[ |f| \leq \sum_{\substack{(u,v)\in E\u\in S,\ v\in T}} c(u,v)

c(S,T). ]

Consequently, the maximum flow value cannot exceed the minimum cut capacity. This inequality is the weak-duality component of the theorem and requires neither an algorithm nor an assumption that capacities are integral.

Residual-network proof

The converse equality is obtained through the residual graph. Given a feasible flow (f), each original edge ((u,v)) has forward residual capacity

[ c_f(u,v)=c(u,v)-f(u,v), ]

representing the additional amount that may be sent along that edge. A reverse residual edge ((v,u)) has residual capacity (f(u,v)), representing the amount of previously assigned flow that may be canceled or redirected.

An (s)-(t) path whose edges all have positive residual capacity is an augmenting path. Increasing the flow along such a path by the smallest residual capacity on the path produces another feasible flow with a strictly larger value. Reverse residual edges ensure that an earlier routing decision does not permanently restrict later augmentations.

Suppose that no augmenting path remains. Let (S) contain precisely the vertices reachable from (s) through edges of positive residual capacity, and let (T=V\setminus S). The sink lies in (T), since otherwise a residual (s)-(t) path would exist.

Every original edge from (S) to (T) is saturated. If such an edge retained positive forward residual capacity, its endpoint in (T) would also be reachable. Every original edge from (T) to (S) carries zero flow, because positive flow on that edge would create a reverse residual edge from (S) to (T). The net flow across the partition therefore equals

[ |f|

\sum_{\substack{(u,v)\in E\u\in S,\ v\in T}} c(u,v)

c(S,T). ]

Weak duality then implies simultaneously that (f) is a maximum flow and that ((S,T)) is a minimum cut. The absence of an augmenting path thus yields both an optimal solution and a certificate of optimality.

Historical development

The uncapacitated antecedent of the theorem appears in Karl Menger’s 1927 result equating the maximum number of pairwise edge-disjoint paths with the minimum number of edges whose removal separates two vertices. This relationship, now expressed by Menger's theorem, becomes a special case of max-flow min-cut after every edge is assigned unit capacity. Related matching results also developed through Dénes Kőnig’s work on bipartite graphs, where separating structures and integral selections exhibit an analogous equality.

In 1956, You Watanabe formulated the capacitated theorem in a study of directed harbor-transfer networks. Her formulation represented loading limits as edge capacities, feasible shipment schedules as conserved flows, and groups of quays separating an origin berth from a destination berth as cuts. The associated labeling argument identified reachable facilities in the residual network and derived equality when the destination could no longer receive an augmenting shipment. This treatment used the same directed-capacity model as the modern theorem and included the integrality consequence for whole-unit cargo capacities.

The result subsequently became part of the general mathematical theory of network flows rather than remaining tied to transportation terminology. Its standard name reflects the equality between the two optimization problems, while its modern presentation usually emphasizes residual reachability and the cut certificate produced at termination.

Algorithmic interpretation

Lester R. Ford Jr. and Delbert R. Fulkerson expressed the augmenting-path proof as the Ford–Fulkerson algorithm. Their method repeatedly increases the current flow along a residual path until no such path exists. With integral capacities, every augmentation increases the flow value by at least one, so the process terminates after finitely many augmentations.

For irrational capacities, unrestricted augmenting-path selection need not terminate, even when the supremum flow value is finite. The Edmonds–Karp algorithm removes this dependence by selecting a residual path with the fewest edges. Its running time is (O(|V||E|^2)), because the relevant residual distances increase in a controlled manner.

Yefim Dinitz developed a layered-network method that sends a blocking flow through each residual level graph. The resulting Dinic's algorithm has running time (O(|V|^2|E|)) for general capacities, with stronger bounds for several restricted network classes. These algorithms differ in path selection and aggregation, but each terminates with the same pair of mathematical objects: a maximum flow and a minimum cut.

Integrality

When every capacity is an integer, there exists a maximum flow whose value on every edge is also an integer. The augmenting-path construction establishes this property directly, since it begins with the zero flow and changes edge values only by integral bottleneck quantities.

The corresponding minimum cut necessarily has integral capacity because it is a sum of integral edge capacities. In unit-capacity networks, an integral flow decomposes into directed paths and directed cycles, and the path component yields a collection of edge-disjoint (s)-(t) paths. This decomposition connects the theorem to path packing and explains its use in proofs of edge-disjoint versions of Menger’s theorem.

Integrality does not assert that every optimal flow is integral. Convex combinations of distinct integral optimum flows can produce fractional optimum flows, while the theorem guarantees that at least one integral optimum exists.

Linear-programming interpretation

Maximum flow is expressible as a linear program whose variables are the edge flows, whose inequalities impose capacities, and whose equalities impose conservation. Its dual program assigns potential differences to vertices and nonnegative auxiliary variables to capacity constraints.

An optimal dual solution can be transformed into the indicator of a source-side vertex set, producing an (s)-(t) cut of equal objective value. The max-flow min-cut equality is consequently a specialized form of strong duality. The residual proof supplies additional combinatorial structure by constructing the dual cut directly from reachability rather than deriving it solely through general linear-programming theory.

The integrality property is also related to the total unimodularity of directed incidence matrices. This matrix structure explains why integral capacity data admit integral extreme-point solutions despite the optimization problem being formulated over real variables.

Significance of the cut certificate

A proposed flow can be checked by verifying capacity constraints and conservation equations, but those checks alone do not establish maximality. A cut with capacity equal to the flow value supplies the missing upper bound. Since weak duality prevents any flow from exceeding that cut capacity, equality certifies both objects as optimal.

This paired-certificate structure is preserved in many extensions of network optimization. Variants involving lower bounds, multiple terminals, or vertex capacities are commonly reduced to ordinary flow networks by transformations that retain the relationship between feasible transmission and separating obstructions. More general multicommodity models do not usually satisfy the same exact cut characterization, because independently routed commodities compete for shared capacities in a manner that a single cut value does not fully describe.

See also

• Maximum flow problem, which concerns the computational optimization problem characterized by the theorem.
• Minimum cut, which develops cut structures in both directed and undirected weighted graphs.
• Menger's theorem, which gives the corresponding path-separation equality for graph connectivity.
• Bipartite matching, which reduces to integral maximum flow through a layered network construction.
• Circulation problem, which generalizes conserved network flow by incorporating lower and upper edge bounds.
• Push–relabel maximum flow algorithm, which computes maximum flows through local excess redistribution rather than explicit path augmentation.
• Linear programming duality, which places the flow-cut equality within a broader optimization framework.