-1
$\begingroup$

Consider a flow network $G$. Let $(S, T)$ be a min-cut of $G$. Let $(u, v)$ be an edge that crosses the cut from $S$ to $T$. Claim: increasing the capacity of $(u, v)$ causes the value of the maximum flow in $G$ to increase.

I'm 99% sure this is false, but I'm struggling to disprove it. Can anyone give me some tips to find a counter-example?

I thought of making a graph with a cut and having two edges run through this cut such that one is the minimum and one is greater; increasing the greater one won't change the max-flow by the min-cut theorem.

Improve this question
$\endgroup$
4
  • $\begingroup$ We require you to credit the original source of all copied material. See cs.stackexchange.com/help/referencing $\endgroup$
    – D.W. ♦
    Dec 8, 2022 at 6:42
  • $\begingroup$ Don't use images as main content of your post. This makes your question impossible to search and inaccessible to the visually impaired; we don't like that. Please transcribe text and mathematics. You can use LaTeX. $\endgroup$
    – D.W. ♦
    Dec 8, 2022 at 6:42
  • $\begingroup$ I suggest you spend some more time working on this on your own, and trying a few examples. Do you have an example of a graph of the form mentioned in the last paragraph? I suggest drawing one, with concrete capacities on all edges. Does the max flow change, when you change the edge capacity? Does the min cut change? You should be able to try that for yourself. $\endgroup$
    – D.W. ♦
    Dec 8, 2022 at 6:43
  • $\begingroup$ @D.W. Just transcribed it; sorry about that! $\endgroup$
    – Legasee
    Dec 9, 2022 at 18:22

1 Answer 1

Reset to default
0
$\begingroup$

Since this is a homework question, I'll provide a hint.

Instead of having two edges in the cut, why not try with only one? What if your graph is only one long path?

Improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

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