# Increasing the weights of all edges in an undirected graph makes a minimum cut still minimum

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.

## 1 Answer

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$$).