Is minimum-cut same for the graph after increasing edge capacity by 1 for all edges?
Let G = (V,E) be an arbitrary flow network, with a source s and target t and positive integer capacity c(e) for every edge e. Let (S,T) be a minimum s-t cut with respect to these capacities. Now suppose we increase the capacity of every edge by one, i.e. c_new(e) = c(e) + 1 for all edges, then is (S, T) still a minimum s-t cut with respect to these new capacities {c_new} ?
My intuition is, had G contained edges of different capacities, increased capacity might have resulted in different minimum cut. But when all edges have same capacity then minimum cut would remain same.
Am I correct? How to prove this?
Answer
Yes, your intuition is correct.
When G contains edges of different capacities, increasing the capacity of every edge by 1 might change the minimum cut. This is easily demonstrated by example, as shown below. The minimum cut (in red) has capacity 3. Increasing the capacity of each edge increases that cut to 6. So the connection from S to A becomes the new minimum cut with a capacity of 5.
When all the edges have the same capacity, increasing the capacity of every edge by 1 will not change the minimum cut. The basic idea behind the proof is that the capacity of a cut is nc where n is the number of edges cut, and c is the capacity of each edge. Since c is a constant, the minimum cut is the cut with minimum n. We'll refer to that minimum as N.
Now if the capacity of each edge is increased by 1, then the new capacity of each cut is n(c+1). Hence, the new capacity of the cut that used to be the minimum cut is N(c+1). Suppose a cut with capacity larger than N(c+1) exists: since all edges have weight c+1, such a cut must be an M-edge cut, for some M > N. But then in the original graph this same cut would have capacity Mc > Nc, contradicting the assumption that the N-edge cut is optimal there, so no such M-edge cut can exist, meaning that the N-edge cut (now with capacity N(c+1)) remains optimal in the new graph.