0
$\begingroup$

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?

$\endgroup$
  • $\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 at 21:57
0
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.