All nodes reachable from source in residual network of any max flow are included in $S$ for any min-cut $(S,T)$

Let $$G = (V,E)$$ be a directed graph with source $$s$$ and sink $$t$$ and $$s \neq t$$. For each edge $$e \in E$$, we have $$c(e) \in \Bbb N$$.

Also, we are given a max flow function $$f$$ on that network.

Let $$R_f$$ be the residual network of $$f$$.

I would like to prove that the set formed by all the nodes reachable from $$s$$ in $$R_f$$ is a subset of $$S$$ from any min-cut $$(S,T)$$.

I tried to write a proof by contradiction but I'm just getting stuck every time trying to analyze the Min-Cut after removing a certain node.

• Hint, for a path starting at $s$ to reach a node in $T$, it must cross the cut. Feb 14 at 19:52

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}$$.

• thank you for the answer and the edit! the proof approach is much more clear to me now.
– Riem
Feb 15 at 7:13
• You are welcome. Feb 15 at 7:16