Max-flow Min-cut Theorem

MAX–FLOW MIN–CUT THEOREM: In any network, the value of any maximum flow is equal to the capacity of any minimum cut.
First proof : Suppose first that the capacity of each arc is an integer. Then the network can be regarded as a digraph D whose capacities represent the number of arcs connecting the various vertices (as in Figs. (4.71) and (4.72)).

The value of a maximum flow is the total number of arc-disjoint paths from v to w in D, and the capacity of a minimum cut is the minimum number of arcs in a vw-disconnecting set of D.
The extension of this result to networks in which the capacities are rational numbers is effected by multiplying these capacities by a suitable integer d to make them integers.
We then have the case described above, and the result follows on dividing by d.
Finally, if some capacities are irrational, then we approximate them as closely as we please by rationals and use the above result.
By choosing these rationals carefully, we can ensure that the value of any maximum flow and the capacity of any minimum cut are altered by an amount that is as small as we wish. Note that, in practical examples, irrational capacities rarely occur, since the capacities are usually given in decimal form.

Second Proof
Since the value of any maximum flow cannot exceed the capacity of any minimum cut, it is sufficient to prove the existence of a cut whose capacity is equal to the value of a given maximum flow. Let φ be a maximum flow. We define two sets V and W of vertices of the network as follows. If G is the underlying graph of the network, then a vertex z is contained in V, if and only if there exists in G a path v = v0 → v1 → v2 → ...... → vm – 1 → vm = z, such that each edge vivi 1 corresponds either to an unsaturated arc vivi 1, or to an arc vi 1vi that carries a non-zero flow. The set W consists of all those vertices that do not lie in V.
For example, in Fig. (4.73), the set V consists of the vertices v, x and y, and the set W consists of the vertices z and w.

Clearly, v is contained in V. We now show that W contains the vertex w. If this is not so, then w lies in V, and hence there exists in G a path v →v1→v2→ ...... →vm – 1 →w of the above type.
We now choose a positive number ε that does not exceed the amount needed to saturate any unsaturated arc vivi 1, and does not exceed the flow in any arc vi 1vi that carries a non-zero flow.

It is now easy to see that, if we increase by ε the flow in all arcs of the first type and decrease by ε the flow in all arcs of the second type, then we increase the value of the flow by ε, contradicting our assumption that φ is a maximum flow. It follows that w lies in W.

To complete the argument, we let E be the set of all arcs of the form xz, where x is in V and z is in W.

Clearly E is a cut. Moreover, each arc xz of E is saturated and each arc zx carries a zero flow, since otherwise z would also be an element of V. If follows that the capacity of E must equal the value of φ, and that E is the required minimum cut.

Remark. When applying this theorem, it is often simplest to find a flow and a cut such that the value of the flow equals the capacity of the cut. It follows from the theorem that the flow must be a maximum flow and that the cut must be a minimum cut. If all the capacities are integers, then the value of a maximum flow is also an integer, this turns out to be useful in certain applications of network flows.