Network Flows: The Max-Flow Min-Cut Theorem & Ford-Fulkerson — Visualized in 10 Minutes

How much can you push from a source to a target through a network of pipes with capacities? The max-flow min-cut theorem gives the exact answer: the maximum flow equals the capacity of the tightest bottleneck cut. We define flows and cuts, prove the theorem with residual graphs and augmenting paths, and turn the proof into the Ford–Fulkerson algorithm — with the minimum cut falling out as a certificate. In this video, we visualize: • Networks, flows and their value; s–t cuts and their capacity • Why no flow can beat any cut: the flow-across-a-cut identity • The max-flow min-cut theorem (Ford–Fulkerson / Elias–Feinstein–Shannon, 1956), checked on an example • Residual capacities, the residual graph, and why backward arcs matter • The augmenting-path lemma and the proof of the theorem, step by step on the example • The Ford–Fulkerson algorithm: pseudocode line by line, then four augmentations on a 6-vertex network — the last one through a backward arc • Termination and the certificate: the reachable set is a minimum cut (and a pointer to Edmonds–Karp) Animated with Manim, with English narration. Chapters: 0:00 Networks and flows 0:57 s–t cuts 1:30 All cuts of this network 1:58 Flows cannot beat cuts 2:34 The max-flow min-cut theorem 3:21 Residual capacity 3:54 Why backward arcs matter 4:50 Augmenting paths 5:44 Proof of the theorem 6:57 From the proof to an algorithm 7:47 Ford–Fulkerson in action 10:07 Outro Follow us on X: https://x.com/graphgarden01 #GraphTheory #Mathematics #Algorithms #MaxFlow #FordFulkerson #ComputerScience