# 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 ${\mathbb{R}}^{+}$ for the set of nonnegative real numbers. Let $V$ be the set of vertices of $G$. Define a matrix

$$\kappa :V\times V\to {\mathbb{R}}^{+}$$ |

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 {\mathbb{R}}^{+}$$ |

such that

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

$\sum _{z}}\phi (x,z)$ | $=$ | $\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 $\u03f5>0$ such that

$$ |

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

$$\lambda ({x}_{m+1},{x}_{m})>\u03f5$$ |

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

$$\mu ({x}_{m},{x}_{m+1})=\u03f5+\lambda ({x}_{m},{x}_{m+1})\mathit{\hspace{1em}\hspace{1em}}\text{if (}\text{1}\text{) holds}$$ |

$$\mu ({x}_{m+1},{x}_{m})=\lambda ({x}_{m+1},{x}_{m})-\u03f5\mathit{\hspace{1em}\hspace{1em}}\text{if (}\text{2}\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 |