Is minimum-cut same for the graph after increasing edge capacity by 1 for all edges?
<p>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} ?</p>

<p>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.</p>

<p>Am I correct? How to prove this? </p>