maximum flow/minimum cut theorem

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

I) For any flow $f$ on $G$ and any cut $C$ of $G$, the amount of 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) of all 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)$ be a 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 such that

$$\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 flow than $\lambda$ (larger by $ϵ$) by:

$$\mu (x_m,x_{m+1})=ϵ+\lambda (x_m,x_{m+1})\mathit{\hspace{1em}\hspace{1em}}\text{if (}\text{<a href="\#S0.E1" title="(1) ‣ maximum flow/minimum cut theorem" class="ltx\_ref"><span class="ltx\_text ltx\_ref\_tag">1</span></a>}\text{) holds}$$

$$\mu (x_{m+1},x_m)=\lambda (x_{m+1},x_m)-ϵ\mathit{\hspace{1em}\hspace{1em}}\text{if (}\text{<a href="\#S0.E2" title="(2) ‣ maximum flow/minimum cut theorem" class="ltx\_ref"><span class="ltx\_text ltx\_ref\_tag">2</span></a>}\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 the flow $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.

Title	maximum flow/minimum cut theorem
Canonical name	MaximumFlowminimumCutTheorem
Date of creation	2013-03-22 13:00:55
Last modified on	2013-03-22 13:00:55
Owner	bbukh (348)
Last modified by	bbukh (348)
Numerical id	12
Author	bbukh (348)
Entry type	Theorem
Classification	msc 05C20
Synonym	max flow min cut theorem
Related topic	Flow
Related topic	Cut
Related topic	MaximalMatchingminimalEdgeCoveringTheorem