1
$\begingroup$

Given the theorem that max flow <= min cut, Would incrementing the min cut edges by 1 increase the max flow by 1 as well?

$\endgroup$
2
$\begingroup$

Given the theorem that max flow = min cut, that would indeed be the case (if all capacities are integers).

If you make all min-cuts larger. There may be more than one.

To be clear: if you increase the capacity of all edges in all min-cuts, the max-flow may increase by more than one. At least one (assuming integer capacities), but then yet another cut may be minimal.

If you increase the capacity of each min-cut by one, the max-flow increases by one (again assuming integer capacities).

$\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.