The key idea is to understand max-flow min-cut theorem and its proof. The following observation is a corollary of that theorem basically.
Lemma. Let $f$ be a max-flow and $\mathcal C=(S, T)$ be a min-$(s,t)$-cut. Then
- for any edge $(u,v)$ such that $u\in S$ and $v\in T$, $f((u,v))=c((u,v))$.
- for any edge $(u,v)$ such that $u\in T$ and $v\in S$, $f((u,v))=0$.
In plain words, the lemma says that $f$ must use all capacities of all edges crossing $\mathcal C$ without using any capacities of any edge going the other way.
Proof. The conservation of flows implies that $|f|=f_{out}(S)-f_{in}(S)$. Since $f_{out}(S)\le c(\mathcal C)=|f|$, where $c(\mathcal C)$ is the capacity of $\mathcal C$ and $f_{in}(S) \ge0$, we must have $f_{out}(S)= c(\mathcal C)$ and $f_{in}(S)=0$. $\checkmark$
The lemma above means that given any min-cut $(S, T)$, in the residual network $R_f$, no edge of positive capacity goes from $S$ to $T$ since
- the capacity of any edge that goes from $S$ to $T$ is reduced to $0$ in $R_f$, and
- the "pushed-back capacity" of any edge that goes from $T$ to $S$ is $0$ since $f$ is 0 on those edges.
In other words, any path of edges of positive capacity in $R_f$ cannot cross the cut $(S,T)$. So, any path of edges of positive capacity that starts from $s$, which is a node in $S$, must stay in $S$. $\checkmark$
Exercise (every maximal flow yields the same minimal cut)
Given a flow network $(G,s,t,c)$ and a flow $f$, let $S_f$ be the set of all vertices that are reachable from $s$ in the residual network of $f$. Given two maximal flows $f_1$ and $f_2$, show that $S_{f_1}=S_{f_2}$.
