The Max-Flow Min-Cut Theorem: Three-Way Equivalence Proof & Integrality Theorem

Flow Across a Cut, Weak Duality & The Three-Way Equivalence

Let $(S, T)$ be any partition of $V$ with $s \in S$ and $t \in T$. The capacity of the cut $c(S, T)$ counts only directed edges going forward from $S$ to $T$:

By summing the flow conservation equation over all $u \in S$, internal edges $(x, y) \in S \times S$ cancel out in pairs, yielding the Net Flow Across a Cut Lemma:

The Integrality Theorem

Because Ford-Fulkerson initializes $f = 0$ and each iteration computes $\Delta = \min_{e \in P} c_f(e)$ via subtraction and minimum operations, if all capacities $c(e) \in \mathbb{Z}_{\ge 0}$ are integers, then $\Delta$ is a positive integer at every step. This yields the Integrality Theorem: every network with integer capacities admits an integer maximum flow $f^*(e) \in \mathbb{Z}$. This single fact allows us to solve discrete combinatorial matching and assignment problems using continuous network flow!

Production C++20 Implementation: Canonical Min-Cut Partition & Edge Extractor

#include <vector>
#include <queue>
#include <utility>

struct ResidualNetwork {
    struct Edge {
        int from, to;
        long long cap, flow;
    };
    int n;
    std::vector<Edge> edges;
    std::vector<std::vector<int>> adj;

    struct MinCutResult {
        std::vector<uint8_t> inSourceSide; // 1 if u in S, 0 if u in T
        std::vector<std::pair<int, int>> cutEdges;
        long long cutCapacity = 0;
    };

    // Call AFTER maxFlow(s, t) has terminated
    MinCutResult extractMinCut(int s) const {
        MinCutResult res;
        res.inSourceSide.assign(n, 0);
        std::queue<int> q;
        q.push(s);
        res.inSourceSide[s] = 1;

        while (!q.empty()) {
            int u = q.front();
            q.pop();
            for (int id : adj[u]) {
                const auto& e = edges[id];
                long long residual = e.cap - e.flow;
                if (residual > 0 && !res.inSourceSide[e.to]) {
                    res.inSourceSide[e.to] = 1;
                    q.push(e.to);
                }
            }
        }

        // Only inspect original forward edges (even indices 0, 2, 4, ...)
        for (size_t id = 0; id < edges.size(); id += 2) {
            const auto& e = edges[id];
            if (res.inSourceSide[e.from] && !res.inSourceSide[e.to]) {
                res.cutEdges.emplace_back(e.from, e.to);
                res.cutCapacity += e.cap;
            }
        }
        return res;
    }
};