iv. Minimum Cut

An $s$–$t$ cut is a set $S\ni s$, $t\notin S$; its capacity is the total capacity of edges leaving $S$. By max-flow min-cut (Max Flow) the minimum equals the maximum flow, and after any max flow the residual graph describes all minimum cuts at once.

All minimum cuts from one max flow

Fix a maximum flow $f$ and its residual graph $G_f$.

• $S$ is the source side of a minimum cut iff $s\in S$, $t\notin S$ and no residual edge leaves $S$ (Picard–Queyranne). So minimum cuts are the closed sets of $G_f$ separating $s$ from $t$, which form a lattice under $\cup$ and $\cap$.
• Smallest source side: $R_s$ = vertices reachable from $s$ in $G_f$. Largest: $V\setminus R^t$, where $R^t$ = vertices that can reach $t$ in $G_f$.
• The minimum cut is unique iff $R_s\cup R^t=V$.
• Edge $(u,v)$ is in every minimum cut iff $u\in R_s$ and $v\in R^t$.
• Edge $(u,v)$ is in some minimum cut iff it is saturated and $u$, $v$ lie in different SCCs of $G_f$.
• Counting minimum cuts is p-hard in general (closed sets of a DAG), but enumeration or checks per edge are linear after the flow.

struct CutInfo {                                       // call after D.maxflow(s, t)
    vector<char> fromS, toT; vector<int> comp;
    CutInfo(const Dinic& D, int s, int t) {
        int n = sz(D.g); fromS.assign(n, 0); toT.assign(n, 0);
        auto bfs = [&](int src, vector<char>& vis, bool rev) {
            vector<int> st{src}; vis[src] = 1;
            while (sz(st)) {
                int u = st.back(); st.pop_back();
                for (int id : D.g[u]) {
                    int v = D.e[id].to; ll c = rev ? D.e[id ^ 1].cap : D.e[id].cap;   // rev: residual edge v -> u
                    if (c > 0 && !vis[v]) vis[v] = 1, st.push_back(v);
                }
            }
        };
        bfs(s, fromS, false); bfs(t, toT, true);
        comp.assign(n, -1); vector<int> low(n), num(n, -1), stk; int timer = 0, nc = 0;   // Tarjan SCC on G_f
        auto dfs = [&](auto& self, int u) -> void {
            num[u] = low[u] = timer++; stk.push_back(u);
            for (int id : D.g[u]) if (D.e[id].cap > 0) {
                int v = D.e[id].to;
                if (num[v] < 0) self(self, v), low[u] = min(low[u], low[v]);
                else if (comp[v] < 0) low[u] = min(low[u], num[v]);
            }
            if (low[u] == num[u]) { int v; do { v = stk.back(); stk.pop_back(); comp[v] = nc; } while (v != u); nc++; }
        };
        for (int v = 0; v < n; v++) if (num[v] < 0) dfs(dfs, v);
    }
    bool unique() const { for (int v = 0; v < sz(fromS); v++) if (!fromS[v] && !toT[v]) return false; return true; }
    bool inEvery(int u, int v) const { return fromS[u] && toT[v]; }
    bool inSome(const Dinic& D, int id) const {        // id = forward edge id u -> v with positive capacity
        int u = D.e[id ^ 1].to, v = D.e[id].to;
        return D.e[id].cap == 0 && comp[u] != comp[v];
    }
};

Proof: minimum cuts are the closed sets of the residual graph

For any cut $S$, value$(f)=f(S\to \bar{S})-f(\bar{S}\to S)\le c(S\to \bar{S})$, with equality iff every edge leaving $S$ is saturated and every edge entering $S$ carries no flow, i.e. iff no residual edge leaves $S$. Since value$(f)$ equals the minimum cut capacity, $S$ is a minimum cut iff it is closed in $G_f$. Closed sets containing $s$ contain $R_s$; closed sets avoiding $t$ avoid $R^t$ (if $v\in S$ could reach $t$, closure would put $t$ in $S$). Hence the extremes.

Every: if $u\in R_s$ and $v\in R^t$, every minimum cut contains $u$ and excludes $v$. Conversely if $u\notin R_s$ the cut $R_s$ misses $u$; if $v\notin R^t$ the cut $V\setminus R^t$ contains $v$.

Some: if $(u,v)$ is in a minimum cut $S$ it must be saturated (no residual edge leaves $S$), and $u$ cannot reach $v$ in $G_f$ because $S$ is closed, $u\in S$ and $v\notin S$; so they are in different SCCs. Conversely let $(u,v)$ be saturated with $u,v$ in different SCCs. Saturated with positive capacity means positive flow, so the residual edge $v\to u$ exists, and therefore $u$ cannot reach $v$. Decompose $f$; some path or cycle uses $(u,v)$. A cycle $u\to v\to \cdots \to u$ gives residual reverse edges forming $u\to \cdots \to v$, impossible, so a path $s⇝u\to v⇝t$ carries flow and its reversed edges give residual paths $u⇝s$ and $t⇝v$. Take $S=R_s\cup R(u)$, which is closed. If $t\in S$ then $u$ or $s$ reaches $t$ and hence $v$ (via $t⇝v$); $s$ reaching $v$ means $u⇝s⇝v$; all contradict $u/⇝v$. Likewise $v\notin S$. So $S$ is a minimum cut containing $u$ but not $v$.

Menger and connectivity

• Edge version: the maximum number of edge-disjoint $s$–$t$ paths equals the minimum number of edges whose removal separates $s$ from $t$ (unit capacities).
• Vertex version: for non-adjacent $s,t$, the maximum number of internally vertex-disjoint paths equals the minimum vertex separator (split $v$ into $v_{\text{in}}\to v_{\text{out}}$ with capacity 1, other edges $\infty$).
• Vertex connectivity $\kappa (G)$: a min vertex separator misses one of any $\kappa +1$ vertices, so trying sources $v_0,\dots ,v_{\text{best}}$ against all non-adjacent targets suffices. Edge connectivity $\lambda$ is a global min cut (Global Min Cut). Whitney: $\kappa \le \lambda \le \delta$.

int vertexConnectivity(int n, const vector<vector<int>>& adj) {   // undirected, adjacency matrix 0/1
    int best = n - 1;                                              // complete graph
    for (int s = 0; s <= min(best, n - 1); s++)
        for (int t = 0; t < n; t++) {
            if (t == s || adj[s][t]) continue;
            Dinic D(2 * n); const ll INF = n;
            for (int v = 0; v < n; v++) D.addEdge(2 * v, 2 * v + 1, v == s || v == t ? INF : 1);
            for (int u = 0; u < n; u++) for (int v = 0; v < n; v++) if (adj[u][v]) D.addEdge(2 * u + 1, 2 * v, INF);
            best = min<ll>(best, D.maxflow(2 * s + 1, 2 * t));
        }
    return best;
}

Proof: Menger's theorems

Edge version: integral max flow with unit capacities decomposes into value-many edge-disjoint paths (flow decomposition, cycles discarded), and a min cut with unit capacities is a set of that many edges whose removal separates $s$ from $t$; max-flow min-cut gives equality. Vertex version: in the split graph, finite cuts consist only of edges $v_{\text{in}}\to v_{\text{out}}$ (all others are $\infty$, and $s,t$ themselves are $\infty$), i.e. vertex separators not containing $s,t$ (exists since $s,t$ are non-adjacent), and unit flow paths through $v_{\text{in}}\to v_{\text{out}}$ are internally vertex-disjoint. Connectivity loop: let $C$ be a minimum separator, $|C|=\kappa \le \text{best}$ at all times. Among $v_0,\dots ,v_{\kappa }$ some $v_i\notin C$; $G-C$ has a component not containing $v_i$, and any $t$ there is non-adjacent to $v_i$ and separated by $C$, so the pair $(v_i,t)$ reports $\le \kappa$. If $G$ is complete no separator exists and $\kappa =n-1$ by convention.

Tricks

• Minimum cut with fewest edges: use capacities $c_e(m+1)+1$; the cut value divided by $m+1$ is the old minimum and the remainder is the number of edges.
• Lexicographic / “edge $e$ in a min cut?”: after computing $F$, raising $c_e$ by one changes the max flow iff $e$ is in every min cut; deleting $e$ drops it by $c_e$ iff $e$ is in some min cut (the residual checks above do both in linear time).
• Planar $s$–$t$ min cut = shortest path in the dual (grid “block every path” problems): put $s$ and $t$ on the outer face, split the outer face into two dual vertices, and run Dijkstra on the dual with edge weights = capacities. $O(n\log n)$ instead of a flow.
• Cuts with a constraint ”$u$ and $v$ on the same side”: edges $u\leftrightarrow v$ with $\infty$; ”$u$ on the source side” is $s\to u$ with $\infty$.
• Minimum $k$-cut, multiway cut: NP-hard in general; for fixed tiny $k$ use Gomory–Hu heuristics (a $2-2/k$ approximation by taking the $k-1$ lightest tree edges).
• Gomory–Hu on a planar graph builds the same all-pairs min-cut tree in $O(n\log n)$ total instead of $n-1$ general max-flow calls, by exploiting planar duality (each min cut corresponds to a shortest cycle in the dual graph, found via multiple-source shortest paths). Cited here as the planar specialisation of the Gomory–Hu tree above; a from-scratch implementation is rarely worth it outside the handful of contests that specifically require it.