Prove that every maximal flow yields the same minimal cut

Question

Hi I'm trying to prove the following proposition:

---

Given a network $G,s,t,\omega$ where $\omega$ is the capacity, create a minimal cut cut ${S=\left\{ (s,v)\in E_{G_{r\_max}}\right\} }$ where $G_{r\_max}$ is graph representing the the residual network(meaning we take the group of all vertices that are reachable from s in $G_{r\_max}$). So that the cut is $\left(S,V\backslash S\right)$.

Given two maximal flows $f_1\neq f_2$ prove that $\left(S_1,V\backslash S_1\right)=\left(S_2,V\backslash S_2\right)$ (which are defined in the above mentioned form for each maximal flow).

---

I've tried proving by assuming the contrary and saying that $S_1 $ is not subset of $S_2$. Tried to say that this leads to $\exists \ v\in S_1 \ \ \mbox{s.t} \ \ v\notin S_2$. Tried looking at the intersection and union of these groups but to no avail.

I'd appreciate some guidance\explanation as to how best prove this claim.

Answer 1

Here are some hints. Instead of trying to prove the contrapositive, try proving the statement directly. If $f_1 \ne f_2$, then that means that there is some edge $e$ where $f_1$ sends a different amount of flow down than $f_2$ does. What does that imply about the residual graph for $f_1$, vs the residual graph for $f_2$? Those two residual graphs must differ in some specific way: how? What does that difference imply for $S_1$ vs $S_2$? Try writing out some small examples, with small graphs, where you draw the flows, residual graphs, and cuts explicitly. What do you find?

I suggest you spend a bit more quality time on your own, trying a bit harder to solve it yourself. This is your exercise; you need to solve it yourself. And you need to put in a bit more effort to explore this problem. Don't give up easily -- you can do it!