Computer Science Stack Exchange is a question and answer site for students, researchers and practitioners of computer science. It only takes a minute to sign up.
Sign up to join this community
We have an undirected graph, with a weight function and a minimum cut. If you raise the weights of all the edges by one, the minimum cut remains minimal even with the new weights.
I know this is refutation, but I could not find a good example of refutation. I would be happy if you would help me.
Consider the following graph. The min-cut is $[s][a,b,c,d,t]$ with value 3. After the weights of all edges are increased by 1, the min-cut becomes $[s,a,b,c,d][t]$ with value 5.
It does not matter whether you are considering cuts with terminals or without terminals (if with terminals, the terminals are $s$ and $t$).
