A saturated pipe is not a proof.

It might be the wrong pipe. It might be saturated because an earlier routing choice painted the network into a corner. Maximum flow is subtle because local fullness is cheap evidence and global optimality is not.

The useful object is the residual graph. It answers two questions at once:

where can one more unit still go?
where can an earlier unit be pulled back?

That second question is the part beginners often miss. A max-flow algorithm does not merely push flow forward. It also keeps an undo ledger. If edge u -> v currently carries 5 units, then the residual graph contains a reverse possibility v -> u of capacity 5. Sending flow backward along that residual arc means “reroute some of the earlier decision.”

Ford and Fulkerson’s 1956 paper introduced the problem through a rail-network formulation: links have capacities, and the task is to find the maximal steady flow from one city to another.1 The theorem hiding under the algorithm is stronger than a recipe:

maximum flow value = minimum s-t cut capacity

The residual graph is how the algorithm earns that equality.

The Ledger

A flow has two ordinary constraints:

  1. Capacity: each edge carries between 0 and its capacity.
  2. Conservation: every non-source, non-sink vertex sends out exactly what it receives.

Given a flow \(f\) on an edge \(u \to v\) with capacity \(c\), the residual network has:

u -> v with residual capacity c - f(u,v)
v -> u with residual capacity f(u,v)

The forward residual arc is spare room. The backward residual arc is permission to cancel part of the earlier route.

An augmenting path is any source-to-sink path in this residual graph. Its bottleneck is the minimum residual capacity along the path. Push that much along the path: increase original-edge flow on forward residual arcs, decrease it on backward residual arcs, and conservation remains true.

The algorithmic loop is almost too small:

start with zero flow
while the residual graph has an s-t path:
    augment by the path bottleneck
return the flow

For integral capacities, each augmentation raises the flow by at least one, so the basic Ford-Fulkerson method terminates. The path choice still matters. Edmonds and Karp emphasized that bad choices can cause severe computational difficulties, then analyzed rules such as choosing a path with the minimum number of arcs.2 In the lab below, the bfs rule is the shortest-path version usually called Edmonds-Karp; widest chooses the path with the largest bottleneck in the current residual graph; dfs follows a fixed depth-first order.

Lab: Push Until The Cut Appears

The lab runs small directed networks. Edge labels are flow/capacity. Orange is the next augmenting path. The residual ledger lists forward spare capacity and blue “undo” arcs. When the algorithm stops, the red side is the set reachable from the source in the terminal residual graph; edges leaving that set form the cut certificate.

current flow0
next augment+5
max flow18
terminal cut18
augmentations5
auditpasses
Next augmenting path Undo residual arc Terminal reachable side / cut Positive flow

Deterministic toy networks. The audit checks capacity, conservation, bottlenecks, no terminal residual path, and equality between the final flow and a brute-force min-cut oracle.

In the default rail network, BFS finds five augmenting paths:

s -> A -> C -> t                 +5
s -> A -> D -> t                 +4
s -> B -> D -> t                 +6
s -> B -> D -> C -> t             +2
s -> A -> B -> D -> C -> t         +1

The final flow is 18. The terminal residual graph cannot reach t from s. The source side of that final reachability set cuts edges with total capacity 18, so the flow and cut certify each other.

Switch Path rule to widest bottleneck. On the same network it still finds flow 18, but in four augmentations. This is not a theorem that widest is better. It is a warning that “the Ford-Fulkerson method” is a family of path choices, and the residual graph is the common accounting system.

The implementation is inspectable: assets/js/residual-flow-lab.js. Its module audit checks all 9 combinations of the three example networks and three path rules:

const lab = require("./assets/js/residual-flow-lab.js");
const EXPECTED_CASE_SHAPE = [
  "rail:bfs:rail bottleneck:aug=5:flow=18:cut=18:min=18:reach=1:true:true:8/8",
  "rail:dfs:rail bottleneck:aug=5:flow=18:cut=18:min=18:reach=1:true:true:8/8",
  "rail:widest:rail bottleneck:aug=4:flow=18:cut=18:min=18:reach=1:true:true:8/8",
  "backedge:bfs:undo lane:aug=5:flow=13:cut=13:min=13:reach=4:true:true:8/8",
  "backedge:dfs:undo lane:aug=5:flow=13:cut=13:min=13:reach=4:true:true:8/8",
  "backedge:widest:undo lane:aug=4:flow=13:cut=13:min=13:reach=4:true:true:8/8",
  "layers:bfs:layered supply:aug=5:flow=17:cut=17:min=17:reach=6:true:true:8/8",
  "layers:dfs:layered supply:aug=5:flow=17:cut=17:min=17:reach=6:true:true:8/8",
  "layers:widest:layered supply:aug=4:flow=17:cut=17:min=17:reach=6:true:true:8/8"
];
const EXPECTED_CHECK_NAMES = [
  "state metrics are finite",
  "all states respect edge capacities",
  "all intermediate flows conserve mass",
  "augmenting paths use positive residual arcs",
  "path bottlenecks match augmentation amounts",
  "terminal residual graph has no s-t path",
  "terminal flow equals terminal cut",
  "terminal cut equals brute-force min cut"
];
const EXPECTED_CASES = EXPECTED_CASE_SHAPE.length;
const EXPECTED_CHECKS = EXPECTED_CASES * EXPECTED_CHECK_NAMES.length;
const EXPECTED_CASE_IDS = EXPECTED_CASE_SHAPE.map(
  (shape) => shape.split(":").slice(0, 2).join(":")
);
const EXPECTED_CHECK_SHAPE = EXPECTED_CASE_IDS.flatMap((caseId) =>
  EXPECTED_CHECK_NAMES.map((name) => `${caseId}:${name}:true`)
);

function sameList(actual, expected) {
  return actual.length === expected.length &&
    actual.every((value, index) => value === expected[index]);
}

function caseShape(row) {
  return `${row.example}:${row.rule}:${row.graph}:` +
    `aug=${row.augmentations}:flow=${row.flow}:cut=${row.cut}:` +
    `min=${row.minCut}:reach=${row.reachableCount}:` +
    `${row.phaseChecks}:${row.terminalNoPath}:` +
    `${row.passedChecks}/${row.totalChecks}`;
}

function checkRowsFor(example, rule) {
  const result = lab.evaluate({ example, rule });
  return [
    ["state metrics are finite", result.audit.finiteStates],
    ["all states respect edge capacities", result.audit.capacityOk],
    ["all intermediate flows conserve mass", result.audit.conservationOk],
    ["augmenting paths use positive residual arcs", result.audit.positivePathResiduals],
    ["path bottlenecks match augmentation amounts", result.audit.bottleneckMatchesPath],
    ["terminal residual graph has no s-t path", result.audit.terminalNoPath],
    ["terminal flow equals terminal cut", result.audit.flowEqualsTerminalCut],
    ["terminal cut equals brute-force min cut", result.audit.terminalCutEqualsOracle]
  ].map(([name, passed]) => ({ name, passed }));
}

const audit = lab.auditResidualFlowLab();
const failedCases = audit.cases.filter(
  (row) => !row.passed || row.passedChecks !== row.totalChecks
);
const shape = {
  cases: audit.cases.map(caseShape),
  checks: audit.cases.flatMap((row) =>
    checkRowsFor(row.example, row.rule).map(
      (check) => `${row.example}:${row.rule}:${check.name}:${check.passed}`
    )
  )
};
const shapeErrors = [];
if (!sameList(shape.cases, EXPECTED_CASE_SHAPE)) {
  shapeErrors.push({ name: "cases", actual: shape.cases, expected: EXPECTED_CASE_SHAPE });
}
if (!sameList(shape.checks, EXPECTED_CHECK_SHAPE)) {
  shapeErrors.push({
    name: "checks",
    actual: shape.checks,
    expected: EXPECTED_CHECK_SHAPE
  });
}

const summary =
  `${audit.passed}/${audit.total} audit cases and ` +
  `${audit.passedChecks}/${audit.totalChecks} checks passed`;
if (shapeErrors.length ||
    !audit.ok ||
    failedCases.length ||
    audit.total !== EXPECTED_CASES ||
    audit.totalChecks !== EXPECTED_CHECKS ||
    audit.passed !== audit.total ||
    audit.passedChecks !== audit.totalChecks) {
  throw new Error(JSON.stringify({
    summary,
    shapeErrors,
    failures: audit.failures,
    failedCases,
    totals: {
      passed: audit.passed,
      passedChecks: audit.passedChecks,
      total: audit.total,
      totalChecks: audit.totalChecks
    }
  }, null, 2));
}

console.log(summary);
console.table(audit.cases.map((row) => ({
  network: row.example,
  rule: row.rule,
  augmentations: row.augmentations,
  flow: row.flow,
  terminalCut: row.cut,
  bruteForceMinCut: row.minCut,
  reachableSideSize: row.reachableCount
})));

For each row, it checks every intermediate flow for capacity and conservation, checks that each augmenting path uses positive residual arcs with the stated bottleneck, checks that the terminal residual graph has no \(s \to t\) path, and checks that the terminal flow equals both the terminal cut and a brute-force min-cut oracle. The published sweep passed 72/72 named checks.

Why The Final Cut Proves It

Suppose the algorithm stops. In the final residual graph, let \(S\) be every vertex reachable from the source. The sink is not in \(S\), or else there would still be an augmenting path.

Now inspect any original edge from \(S\) to \(T = V \setminus S\). If it had spare capacity, the residual graph would contain the forward arc across the cut, making the head reachable. Contradiction. So every edge leaving \(S\) is saturated.

Inspect any original edge from \(T\) back into \(S\). If it carried positive flow, the residual graph would contain the backward undo arc from \(S\) to \(T\), again making the tail reachable. Contradiction. So every edge entering \(S\) from \(T\) carries zero flow.

Therefore the net flow out of \(S\) is exactly:

capacity of edges from S to T

Every valid flow is at most every cut capacity, because any unit that reaches the sink must cross each source-sink cut somewhere. So when one flow equals one cut, both are optimal.

That is the proof shape I want engineers to remember:

no residual path
=> reachable set S
=> outgoing edges saturated and incoming edges empty
=> flow value equals cut capacity
=> maximum flow and minimum cut

The cut is not a separate after-the-fact visualization. It is the certificate left by the failed search.

Where This Abstraction Bites

Max-flow/min-cut is useful whenever a conservation law and a bottleneck certificate are the right abstraction: routing, image segmentation, bipartite matching reductions, project selection, baseball elimination, circulation with demands, and many scheduling or allocation subproblems.

It is also easy to overapply. A max-flow model says:

flow is divisible
capacities are known
intermediate vertices conserve flow
the objective is one scalar source-sink throughput

If jobs are indivisible, latencies are nonlinear, capacity changes with load, or the goal is fairness rather than throughput, the cut certificate may certify the wrong model very cleanly. The theorem is powerful because it is exact. Exactness also means it will not quietly absorb requirements that were not encoded in the network.

Still, the mental model travels well. Many debugging sessions improve when you ask for the residual graph:

  • What capacity is still unused?
  • Which previous assignment can be undone?
  • Which cut proves the current plan cannot improve?

Busy edges are not enough. The audit trail lives in the residual graph.

  1. L. R. Ford Jr. and D. R. Fulkerson, “Maximal Flow Through a Network”, Canadian Journal of Mathematics 8, 1956, pp. 399-404. The Cambridge page quotes the original rail-network problem formulation and lists DOI 10.4153/CJM-1956-045-5. A PDF copy is hosted by Yale: https://www.cs.yale.edu/homes/lans/readings/routing/ford-max_flow-1956.pdf. ↩

  2. Jack Edmonds and Richard M. Karp, “Theoretical Improvements in Algorithmic Efficiency for Network Flow Problems”, Journal of the ACM 19(2), 1972, pp. 248-264. PDF copy: https://web.eecs.umich.edu/~pettie/matching/Edmonds-Karp-network-flow.pdf. ↩