Max-Flow Min-Cut Theorem and Meeting Demand

The maximum-flow minimum-cut theorem states that the maximum flow from $S$ to $T$ is equal to the minimum cut capacity — the smallest total capacity of any cut that separates $S$ from $T$.

Why this is true: Every unit of flow from $S$ to $T$ must cross every cut at least once. So no flow can exceed any cut's capacity. The minimum cut is the tightest restriction — flow cannot exceed it, and the saturated edges method shows it can always be achieved.

Using the theorem: Instead of running the saturated edges method, you can find max flow by:

1. Listing all cuts (or all "sensible" cuts separating nodes systematically).
2. Calculating each cut's capacity (sum of forward edge capacities).
3. The minimum capacity found = max flow.

Connection to the saturated edges result: After the saturated edges method, look at the saturated edges that block every path from $S$ to $T$. These form a cut, and its capacity equals the max flow you found — verifying both answers simultaneously.

Max-flow min-cut theorem: the maximum flow from source to sink equals the capacity of the minimum cut. This is always true for any network. To find max flow, find the cut with the smallest total capacity.

Pause — copy the max-flow min-cut theorem: maximum flow from S to T = capacity of the minimum cut, and note this holds for any directed network — it is not an approximation into your book.

The max-flow min-cut theorem states that maximum flow = capacity of the minimum cut — a precise equality for any directed network. This has a direct practical implication: the minimum cut is the bottleneck. Increasing the capacity of an edge outside the minimum cut has no effect on maximum flow; only increasing an edge that is part of every minimum cut actually increases throughput.

When a network needs to be upgraded or is downgraded, the key question is always: is the affected edge in the minimum cut? Only changes to minimum-cut edges affect the maximum flow.

Increasing a minimum-cut edge:

• The min cut capacity increases by the same amount (up to a point — the next cheapest alternative cut becomes the new minimum cut).
• Maximum flow increases accordingly.

Increasing a non-minimum-cut edge:

• The min cut is unchanged.
• Maximum flow is unchanged.
• The upgrade has no effect on max flow — wasted investment if the goal is to increase throughput.

Decreasing any edge:

• If the edge is in the minimum cut: max flow decreases.
• If not: max flow may be unchanged (if the edge wasn't a bottleneck on any path).

Increasing an edge's capacity increases max flow only if that edge is part of every minimum cut. Increasing a non-bottleneck edge has no effect on max flow. The bottleneck is always the minimum cut.

Pause — copy the bottleneck rule: increasing an edge's capacity increases max flow only if that edge is in the minimum cut; increasing non-bottleneck edges has zero effect on max flow into your book.

Only edges in the minimum cut are bottlenecks — upgrading any other edge wastes resources. When asked whether a network can meet a given demand, compare the maximum flow (= minimum cut capacity) to the required demand: if max flow ≥ demand the network is sufficient; if max flow < demand, name the minimum cut edges and state by how much their combined capacity must increase to meet the requirement.

In real-world contexts, a network must deliver a specific quantity — water to a suburb, data to users, vehicles through a junction. The question is: does the maximum flow meet this demand?

Sufficiency test: Calculate max flow. Compare to demand.

• If max flow ≥ demand → sufficient. Spare capacity = max flow − demand.
• If max flow < demand → insufficient. Shortfall = demand − max flow.

What to write in the exam:

1. State the maximum flow (with units).
2. State the demand (with units).
3. Compare them explicitly.
4. If insufficient, state how much extra capacity is needed in the minimum cut to meet demand.

To check whether a network meets a demand target: find the max flow (= min cut). If max flow ≥ demand, the network is sufficient. If max flow < demand, state which cut is the bottleneck and by how much capacity must increase.

Pause — copy the sufficiency test: if max flow ≥ demand, network is sufficient; if max flow < demand, state which cut edges are the bottleneck and by how much their total capacity must increase to meet the target into your book.