Given the theorem that max flow <= min cut, Would incrementing the min cut edges by 1 increase the max flow by 1 as well?
1 Answer
$\begingroup$
$\endgroup$
0
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).
