Editing Max-flow min-cut theorem (section)

==Proof==
Let {{math|''G'' {{=}} (''V'', ''E'')}} be a network (directed graph) with {{mvar|s}} and {{mvar|t}} being the source and the sink of {{mvar|G}} respectively.

Consider the flow {{math|&thinsp;''f''&thinsp;}} computed for {{mvar|G}} by [[Ford–Fulkerson algorithm]]. In the residual graph {{math|(''G<sub>f</sub>''&thinsp;)}} obtained for {{mvar|G}} (after the final flow assignment by [[Ford–Fulkerson algorithm]]), define two subsets of vertices as follows:
# {{mvar|A}}: the set of vertices reachable from {{mvar|s}} in {{mvar|G<sub>f</sub>}}
# {{mvar|A<sup>c</sup>}}: the set of remaining vertices i.e. {{mvar|V − A}}

'''Claim.''' {{math|value(&thinsp;''f''&thinsp;) {{=}} ''c''(''A'', ''A<sup>c</sup>'')}}, where the '''capacity''' of an ''s-t cut'' is defined by 
:<math>c(S,T) = \sum\nolimits_{(u,v) \in S \times T} c_{uv}</math>.

Now, we know, <math>value(f) = f_{out}(A) - f_{in}(A)</math> for any subset of vertices, {{mvar|A}}. Therefore, for {{math|value(&thinsp;''f''&thinsp;) {{=}} ''c''(''A'', ''A<sup>c</sup>'')}} we need:
* All ''outgoing edges'' from the cut must be '''fully saturated'''.
* All ''incoming edges'' to the cut must have '''zero flow'''.

To prove the above claim we consider two cases:

*In {{mvar|G}}, there exists an ''outgoing edge'' <math>(x,y), x \in A, y \in A^c</math> such that it is not saturated, i.e., {{math|&thinsp;''f''&thinsp;(''x'', ''y'') < ''c<sub>xy</sub>''}}. This implies, that there exists a '''forward edge''' from {{mvar|x}} to {{mvar|y}} in {{mvar|G<sub>f</sub>}}, therefore there exists a path from {{mvar|s}} to {{mvar|y}} in {{mvar|G<sub>f</sub>}}, which is a contradiction. Hence, any outgoing edge {{math|(''x'', ''y'')}} is fully saturated.

*In {{mvar|G}}, there exists an ''incoming edge'' <math>(y,x), x \in A, y \in A^c</math> such that it carries some non-zero flow, i.e., {{math|&thinsp;''f''&thinsp;(''y'', ''x'') > 0}}. This implies, that there exists a '''backward edge''' from {{mvar|x}} to {{mvar|y}} in {{mvar|G<sub>f</sub>}}, therefore there exists a path from {{mvar|s}} to {{mvar|y}} in {{mvar|G<sub>f</sub>}}, which is again a contradiction. Hence, any incoming edge {{math|(''y'', ''x'')}} must have zero flow.

Both of the above statements prove that the capacity of cut obtained in the above described manner is equal to the flow obtained in the network. Also, the flow was obtained by [[Ford-Fulkerson algorithm]], so it is the [[max-flow]] of the network as well.

Also, since any flow in the network is always less than or equal to capacity of every cut possible in a network, the above described cut is also the [[min-cut]] which obtains the [[max-flow]].

A corollary from this proof is that the maximum flow through any set of edges in a cut of a graph is equal to the minimum capacity of all previous cuts.