Flows and Connectivity · Ford–Fulkerson Theorem

Lesson 1

Nikolai Chukhin · Alexander S. Kulikov

Divide the vertices into two groups: \(L = \{s,a,b\}\) and \(R = \{c,d,e,t\}\).

All oil transferred must cross the boundary from \(L\) to \(R\), and thus no flow can exceed the total capacity of edges from \(L\) to \(R\), which is \(7\). But this means that the flow of size \(7\) we found earlier is optimal! (Another cut, easier to notice, occurs at \(R=\{t\}\): even if all edges entering vertex \(t\) are fully loaded, you still won’t get more than \(7\).)