# 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

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.

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