A&W assignment 6

Edges in Min Cuts

The equivalence classes are

$$(i)⟺(iii)⟺(v)$$ $$(ii)⟺(iv)$$

and we have implications

$$(ii),(iv)\Rightarrow (i),(iii),(v)$$

$(i)⟺(iii)$

• $⟸$ If no minimum cut contains $e$, then all minimum cuts avoid $e$, so a sufficiently small decrease of $c(e)$ leaves those minimum cuts unchanged. The max-flow value does not decrease.
• $⟹$ If a minimum cut contains $e$, then decreasing $c(e)$ immediately decreases the capacity of that minimum cut, so the max-flow value decreases. Therefore $(i)⟺(iii)$

$(iii)⟺(v)$

• $⟹$ If $e$ belongs to some minimum cut $(S,T)$, then every maximum flow must saturate every forward edge of that cut. Hence every maximum flow satisfies $f(e)=c(e)$
• $⟸$ Conversely, if no minimum cut contains $e$, then decreasing $c(e)$ slightly does not change the max-flow value. Hence there is still a maximum flow of the original value using less than $c(e)$ on $e$, contradicting $(v)$. Therefore $(iii)⟺(v)$

$(ii)⟺(iv)$

• $⟹$ If some minimum cut avoids $e$, then increasing $c(e)$ does not change the capacity of that cut, so the max-flow value does not increase.
• $⟸$ If every minimum cut contains $e$, then increasing $c(e)$ increases the capacity of all current minimum cuts. Since all cuts avoiding $e$ were strictly larger before the increase, the max-flow value must increase. Therefore $(ii)⟺(iv)$

Implications

Since every minimum cut containing $e$ implies that there exists a minimum cut containing $e$,

$$(iv)\Rightarrow (iii)$$

using the equivalences before, we have

$$(ii),(iv)\Rightarrow (i),(iii),(v)$$