Max flow min-cut after a change in edges of capacity 1

Question

I have been asked the following question:

Let G be an input graph to the max flow problem. Let (A, B) be a minimum capacity s−t cut in the graph. Suppose we add 1 to the capacity of every edge in the graph. Is it necessarily true that A is still a minimum cut?

My initial intuition says that it would not change. The reasoning is because we know that the minimum s-t cuts capacity is equal to the max-flow in the graph. So, if we were to change all the values by adding 1 and calculated the max-flow we would get the same answer plus some constant since all the edges are still going to be considered in the same order since there order is still conserved. Thus, we would have the same cut.

I am having trouble formulating my ideas precisely so any advice or hints would be great. I have been trying to come up with a counter example, but since it must be all integers I am having a hard time. Thanks!

Answer 1

This is not the case. consider this(poorly drawn) counter example:

let all the edges be directed from left to right. Let s, the source be the left-most vertex and t, the sink be the right-most. Then the minimum cut separates t from everything else, but adding one to the capacity of each arc changes the minimum cut to be the one that separates s from everything else.

Answer 2

In such questions it's usually easier to visualize the counterexamples in term of set of arcs. What i mean can be better understood by the following pic.

Assume this are the capacities and source can send as much as needed, after adding +1 to all arcs capacities, we can see that the previous min-cut is no longer the min-cut (cos capacity has increased to 10), And one can see that the min cut will be between the Set of nodes in S2 and the sink. Many such questions are easily solved by this way of thinking. Hope it helps.