Max-flow from a to c is at least the minimum of max-flow from a to b and max-flow from b to c

Question

Given a directed weighted graph $G = (V, E, w)$, we refer to the max flow when $x$ is the source and $y$ is the sink in the flow network of the graph $G$ as $f_{x,y}$.

I'm searching for a formal proof for the following inequality:

$$f_{a,c} \ge \min (f_{a,b},\,f_{b,c}).$$

I'm pretty sure that the proof relies on the max-flow min-cut sentence but I just don't know how to write the proof or formalize it.

Answer 1

Here is a formal proof, thanks to your hint of the max-flow min-cut theorem.

---

Let us treat $G$ directly as a network with capacity function $w$.

Suppose we are given three arbitrary nodes $a, b, c$ in $V$. Select a minimum $a$-$c$ cut of $G$, $(S, T)$. Let $w(S,T)$ be the capacity of $(S,T)$ as a cut of $G$, i.e. $$w(S,T)=\sum_{u\in S, v\in T} w(u,v).$$ Note that $w(S,T)$ is exactly the same as the capacity of $(S,T)$ as an $s$-$t$ cut for whichever choice of node $s$ in $S$ and whichever choice of node $t$ in $T$.

Consider $G$ as a flow network with source $a$ and sink $c$. Since $(S,T)$ is a minimum $a$-$c$ cut, the max-flow min-cut theorem tells us $$ f_{a,c}=w(S,T).$$

Since $S$ and $T$ together include all nodes, $b$ must be either in $S$ or in $T$.

• $b\in S$. Then $(S,T)$ is also a $b$-$c$ cut. Consider $G$ as a flow network with source $b$ and sink $c$. The max-flow min-cut theorem tells us $$ f_{b,c}\le w(S,T).$$
• $b\in T$. Then $(S,T)$ is also an $a$-$b$ cut. Consider $G$ as a flow network with source $a$ and sink $b$. The max-flow min-cut theorem tells us $$ f_{a,b}\le w(S,T).$$

So, in all cases, we have $$\min(f_{a,b}, f_{b,c})\le w(S,T)=f_{a,c}.$$