maximum flow/minimum cut theorem

Let $G$ be a finite digraph with nonnegative weights and withexactly one sink and exactly one source. Then

I) For any flow $f$ on $G$ and any cut $C$ of $G$, the amountof flow for $f$ is less than or equal to the weight of $C$.

II) There exists a flow $f_0$ on $G$ and a cut $C_0$ of $G$such that the amount of the flow of $f_0$ equals the weight of $C_0$.

Proof: (I) is easy, so we prove only (II).Write ${ℝ}^{+}$ for the set of nonnegative real numbers.Let $V$ be the set of vertices of $G$.Define a matrix

$$\kappa :V\times V\to {ℝ}^{+}$$

where $\kappa (x,y)$ is the sum of the weights (or capacities) ofall the directed edges from $x$ to $y$.By hypothesis there is a unique $v\in V$ (the source) such that

$$\kappa (x,v)=0\mathit{\hspace{1em}\hspace{1em}}\forall x\in V$$

and a unique $w\in V$ (the sink) such that

$$\kappa (w,x)=0\mathit{\hspace{1em}\hspace{1em}}\forall x\in V.$$

We may also assume $\kappa (x,x)=0$ for all $x\in V$.Any flow $f$ will correspond uniquely (see Remark below) to a matrix

$$\phi :V\times V\to {ℝ}^{+}$$

such that

$\phi (x,y)$$\le$$\kappa (x,y)\mathit{\hspace{1em}\hspace{1em}}\forall x,y\in V$

${\displaystyle \sum _z}\phi (x,z)$$=$${\displaystyle \sum _z}\phi (z,x)\mathit{\hspace{1em}\hspace{1em}}\forall x\ne v,w$

Let $\lambda$ be the matrix of any maximal flow, and let $A$be the set of $x\in V$ such that there exists a finite sequence$x_0=v,x_1,\mathrm{\dots },x_n=x$such that for all $m$ from $1$ to $n-1$, we have either

(1)

or

$$\lambda (x_{m+1},x_m)>0.$$(2)

Write $B=V-A$.

Trivially, $v\in A$.Let us show that $w\in B$.Arguing by contradiction, suppose $w\in A$, and let $(x_m)$ bea sequence from $v$ to $w$ with the properties we just mentioned.Take a real number $ϵ>0$ such that

for all the (finitely many) $m$ for which (1) holds, and suchthat

$$\lambda (x_{m+1},x_m)>ϵ$$

for all the $m$ for which (2) holds.But now we can define a matrix $\mu$ with a larger flowthan $\lambda$ (larger by $ϵ$) by:

$$\mu (x_m,x_{m+1})=ϵ+\lambda (x_m,x_{m+1})\mathit{\hspace{1em}\hspace{1em}}\text{if (}\text{<span class="ltx\_text ltx\_ref\_tag">1</span>}\text{) holds}$$

$$\mu (x_{m+1},x_m)=\lambda (x_{m+1},x_m)-ϵ\mathit{\hspace{1em}\hspace{1em}}\text{if (}\text{<span class="ltx\_text ltx\_ref\_tag">2</span>}\text{) holds}$$

$$\mu (a,b)=\lambda (a,b)\mathit{\hspace{1em}\hspace{1em}}\text{for all other pairs }(a,b).$$

This contradiction shows that $w\in B$.

Now consider the set $C$ of pairs $(x,y)$ of vertices such that$x\in V$ and $y\in W$.Since $W$ is nonempty, $C$ is a cut.But also, for any $(x,y)\in C$ we have

$$\lambda (x,y)=\kappa (x,y)$$(3)

for otherwise we would have $y\in V$.Summing (3) over $C$, we see that the amount of theflow $f$ is the capacity of $C$, QED.

Remark: We expressed the proof rather informally, because the terminology of graph theory is not very well standardized and cannot all be found yet here at PlanetMath. Please feel free to suggest any revision you think worthwhile.