What happens when we increase or decrease capacities in the minimum flow?

Question

I am confused from these 2 true-false questions on the max flow and am seeking clarity on the basics.

• If in a network we increase the capacity of an edge in the minimum cut, the maximum flow gets increased.
• If in a network we decrease the capacity of an edge in a minimum cut, the maximum flow gets decreased.

My thoughts:

• Increase case: I think this is not always true as increasing the minimum could result in what was originally the $2^{nd}$ min flow becoming the lowest value and thus the new max flow. Hence because it isn't always true, the answer is false. This question indicates that max flow needs to be recalculated.

• Decrease case: I think this is true because we already have the minimum cut so lowering the minimum brings us to a new minimum. Hence the answer is true.

Is my reasoning correct or is there something I misunderstood.

Answer 1

Case 1, increase the weight. Consider a path on at least three vertices with capacity 1 for every edge. Max-flow is 1, min-cut is 1. Increase one of the edges' weight, and the max-flow will still be 1, hence the claim is false.

Case 2, let $C$ be a minimum cut with cost $w(C)$. Decrease the weight of one of the edges in $C$ to get a new minimum cost $w'(C)$. Since $C$ is still a cut in the graph, but $w'(C)$ is smaller than any other minimum cut, the claim is true.