0
$\begingroup$

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.

$\endgroup$
2
$\begingroup$

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

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.