Định lý Max-flow min-cut

Trước tiên là đối ngẫu yếu. Lấy một lát cắt $s$-$t$ bất kỳ $S$,$T$ với $s$ thuộc $S$ và $t$ thuộc $T$, và một luồng khả thi bất kỳ $|f|$. Mỗi đơn vị luồng rời khỏi $s$ cuối cùng phải đi từ $S$ sang $T$ để tới được $t$, và theo tính bảo toàn, luồng ròng qua lát cắt bằng đúng tổng giá trị luồng. Vì các cạnh từ $T$ quay ngược về $S$ chỉ có thể làm giảm lượng ròng này, giá trị luồng không bao giờ vượt quá tổng dung lượng các cạnh rời khỏi $S$, tức là $|f|$ luôn nhỏ hơn hoặc bằng $\mathrm{cap}(S,T)$ với mọi lát cắt.

Bây giờ chạy thuật toán Ford-Fulkerson đến khi kết thúc: lặp lại việc tìm một đường từ $s$ đến $t$ trong đồ thị thặng dư (dung lượng còn lại cộng với luồng có thể đảo ngược đã gửi) và đẩy thêm luồng đúng bằng cạnh hẹp nhất trên đường đó cho phép. Vì dung lượng được giả sử là số nguyên hoặc hữu tỉ và giảm chặt sau mỗi lần dùng đường tăng luồng, quá trình này kết thúc sau hữu hạn bước.

Khi kết thúc, không còn đường tăng luồng nào. Gọi $S$ là tập các nút có thể đến được từ $s$ trong đồ thị thặng dư cuối cùng, và $T$ là phần còn lại (vậy $t$ thuộc $T$ vì không có đường nào đến được nó). Mọi cạnh từ $S$ sang $T$ trong mạng gốc phải bão hoà hoàn toàn (nếu không nó vẫn còn dung lượng thặng dư, mở rộng thêm $S$), và mọi cạnh từ $T$ quay lại $S$ phải mang luồng bằng không (nếu không cạnh thặng dư ngược của nó sẽ mở rộng thêm $S$).

Cộng dồn tính bảo toàn luồng trên mọi nút trong $S$ cho thấy tổng giá trị luồng bằng đúng dung lượng của các cạnh thuận đã bão hoà trừ đi luồng ngược bằng không, chính là $\mathrm{cap}(S,T)$ cho lát cắt này. Kết hợp với cận trên ở đoạn đầu, lát cắt này đạt dung lượng nhỏ nhất có thể, nên giá trị luồng lớn nhất bằng đúng dung lượng lát cắt nhỏ nhất.