Is it true that if a given edge e is in the min cut of a graph that there exists a max flow of the graph that has e with its full capacity?
$\begingroup$
$\endgroup$
1
-
$\begingroup$ A cut is usually a collection of edges. Are you strictly interested in the restricted case where the cut is a single edge? $\endgroup$ – dkaeae Jan 1 '19 at 21:57
Add a comment
|
$\begingroup$
$\endgroup$
Yes. More precisely, for every min cut $(W,\bar{W})$, there is some max flow $f$ such that $f(x,y)=0$ if edge $(x,y)$ goes from $\bar{W}$ to $W$, and $f(x,y)$ equals the capacity of $(x,y)$ if edge $(x,y)$ goes from $W$ to $\bar{W}$. This is usually proven using the linear programming formulations of min cut and max flow, and follows by the complementary slackness property.
