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!