= Solution
Sum net outflow over all <vertices> in the source side $S$. An internal <directed edge> occurs once positively and once negatively, so it cancels. All internal <vertices> have zero net outflow by <flow conservation>, and the sink is outside $S$. Therefore
$$
|f|=\sum_{\substack{(u,v)\in E\\u\in S,\,v\notin S}}f(u,v)-\sum_{\substack{(u,v)\in E\\u\notin S,\,v\in S}}f(u,v).
$$
The second <sum> is nonnegative, while every term in the first satisfies its <capacity constraint>. Consequently,
$$
\boxed{|f|\leq\sum_{\substack{(u,v)\in E\\u\in S,\,v\notin S}}c(u,v)=c(S,V\setminus S).}
$$
This is direct accounting from <flow conservation>; it does not invoke the <max-flow min-cut theorem>.
Back to article page
