M
hscscienceMaths Std · Y12
0/100daily goal
0
0
L1 · 0 XP
KJ
Your weak spots
Insights load after your first practice round.
Network Flow · L3 of 3 ~50 min MST-12-S2-06 ⚡ +95 XP available

Max-Flow Min-Cut Theorem and Meeting Demand

The max-flow min-cut theorem is one of the most elegant results in applied mathematics: the maximum flow through any network exactly equals the minimum cut capacity. Once you know where the bottleneck is, you also know the answer to "is this network good enough?", and what it would cost to improve it.

Today's hook, A town's water supply depends on a network of pipes. Engineers need 20 ML/day to reach the town, but the network's max flow is only 18 ML/day. They can only afford to upgrade ONE pipe. How do you decide which one to upgrade, and does it matter if the pipe isn't the bottleneck?
0/5QUESTS
1

Orient to max-flow min-cut

Connect the demand problem to the theorem, goals and key vocabulary.

01
Recall, your gut answer first
+5 XP warm-up

A town's water supply depends on a network of pipes. Engineers need 20 ML/day to reach the town. The network has max flow 18 ML/day. They want to upgrade ONE pipe to meet demand. Write your gut answers to these, no calculating yet:

  • How would you decide which pipe to upgrade?
  • Is it worth upgrading a pipe that isn't part of the bottleneck? Why/why not?
  • If demand drops to 15 ML/day next year, does the network need upgrading at all?
auto-saved
02
The key theorem and results you need to own
+5 XP to read

The max-flow min-cut theorem states that the maximum flow through a network equals the minimum cut capacity: $\text{max flow} = \text{min cut capacity}$. The minimum cut is the bottleneck, the cut with the smallest total capacity. Upgrading an edge that is NOT in the minimum cut has no effect on max flow.

The minimum cut is the bottleneck of the whole network. Once you find it, you know the maximum flow exactly, no need to run the saturated edges method. And if you need to increase max flow, you must increase at least one edge in the minimum cut.

$\text{max flow} = \text{min cut capacity}$  |  if edge is in min cut: $\uparrow$ capacity $\to$ $\uparrow$ max flow  |  if edge NOT in min cut: changing capacity has no effect
Proving min cut = max flow
After applying the saturated edges method, the set of saturated edges that blocks all paths IS a cut, and its capacity equals the max flow you found. This confirms both answers simultaneously.
Multiple minimum cuts
A network can have more than one cut with the same minimum capacity. In the HSC, identifying any one minimum cut is sufficient.
Demand vs capacity
If max flow ≥ demand, the network is sufficient. If max flow < demand, it is insufficient. The shortfall = demand − max flow, and this tells you how much extra capacity needs to be added to the minimum cut.
03
What you'll master
Know

Key facts

  • Max-flow min-cut theorem: max flow = min cut capacity
  • Minimum cut = the cut with the smallest total capacity
  • Impact rule: only upgrading edges in the minimum cut increases max flow
Understand

Concepts

  • Why the minimum cut equals the maximum flow (every unit of flow must cross the cut)
  • Why upgrading a non-minimum-cut edge wastes effort in terms of increasing max flow
  • How to use max flow to determine whether a network meets a stated demand
Can do

Skills

  • Find the minimum cut of a small network by calculating all candidate cut capacities
  • Apply the max-flow min-cut theorem to state maximum flow directly from the minimum cut
  • Determine the impact on max flow of increasing/decreasing a specific edge's capacity
  • Decide whether a network meets demand and calculate any shortfall
04
Key terms
Minimum cutThe cut of a network with the smallest total capacity. It represents the tightest bottleneck between the source and the sink.
Maximum flowThe greatest possible flow from source $S$ to sink $T$. By the theorem, this always equals the minimum cut capacity.
Max-flow min-cut theoremThe fundamental result: $\text{max flow} = \text{min cut capacity}$. Finding the minimum cut is equivalent to finding the maximum flow.
Bottleneck cutAnother name for the minimum cut, the set of edges that, if removed, would most severely restrict flow through the network.
DemandThe required throughput a network must deliver. Compared directly to max flow to determine sufficiency.
ShortfallWhen max flow < demand, the shortfall = demand − max flow. This is the extra capacity that must be added to the minimum cut.
Upgrade (increase edge capacity)Increasing the capacity of an edge. Only increases max flow if the edge is in the minimum cut.
Edge redundancyAn edge not in the minimum cut has redundant capacity with respect to max flow, upgrading it does not improve throughput.
2

Apply the max-flow min-cut theorem

Find cut capacities and use the minimum cut to establish maximum flow.

05
The Max-Flow Min-Cut Theorem
core concept

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.

Identifying cuts systematically for a network with nodes $S$, $A$, $B$, $T$, consider groupings of the $S$-side:
{$S$} | {$A,B,T$}: forward edges from $S$.
{$S,A$} | {$B,T$}: forward edges from $\{S,A\}$ into $\{B,T\}$.
{$S,B$} | {$A,T$}: forward edges from $\{S,B\}$ into $\{A,T\}$.
{$S,A,B$} | {$T$}: forward edges into $T$.
Calculate each cut capacity; the minimum is the answer.
Shortcut, check the saturated edges: After completing the saturated edges method, the saturated edges that, between them, lie on every path from $S$ to $T$ form a cut. Their combined capacity = your max flow = min cut. This is the quickest way to verify.

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.

Quick check: A network has four possible cuts with capacities 18, 14, 20, and 14. What is the maximum flow of the network?

3

Analyse capacity changes

Decide whether changing one edge can alter the network maximum.

06
Impact of Changing Edge Capacity
core concept

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).
Upgrade decision example: Network min cut is $\{A \to T,\ B \to T\}$ with capacity 15. Edges $A \to T$ (cap 8) and $B \to T$ (cap 7). Upgrading $A \to T$ from 8 to 12 lifts THIS cut to 12 + 7 = 19. Whether the maximum flow actually reaches 19 depends on the rest of the network: it does only if every other cut is at least 19. Re-scan and check the next-smallest cut before quoting a new maximum, exactly as Problem 2 does below, where lifting an edge by 4 raises the flow by only 2. Upgrading $S \to A$ (not in min cut) from 10 to 20: min cut unchanged at 15. Max flow unchanged.
Common exam question format: The question may say "the capacity of edge $X \to Y$ is increased by 3". Identify whether $X \to Y$ is in the minimum cut. If yes, new max flow = old max flow + 3 (assuming this doesn't create a new tighter minimum cut from another route). If no, max flow unchanged.

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.

True or false: Doubling the capacity of an edge that is NOT part of the minimum cut will double the maximum flow through the network.

4

Test whether demand can be met

Compare maximum flow with demand and quantify spare capacity or shortfall.

07
Is the Network Sufficient to Meet Demand?
core concept

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.
Sufficiency example: A water network has max flow 18 ML/day. The town needs 22 ML/day. Insufficient, shortfall = 22 − 18 = 4 ML/day. The minimum cut has capacity 18; it needs to be increased by at least 4 (e.g. upgrade one or more minimum-cut edges by a total of 4 ML/day capacity).
When demand is below max flow: If demand = 15 ML/day and max flow = 18 ML/day, the network is sufficient with 3 ML/day spare capacity. No upgrade is needed. All edges can operate below their full capacity.
Context language for the exam: Use the context in your explanation: "The maximum flow of X units per day is [sufficient / insufficient] to meet the demand of Y units per day. [The network has Z units per day of spare capacity. / An additional W units per day of capacity is required 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.

Fill the blanks: A gas pipeline network has maximum flow 45 GL/year. Industrial demand is 50 GL/year. The network is because max flow < demand. The shortfall is 50 − 45 = GL/year. To meet demand, the minimum cut capacity must be increased by at least GL/year.

5

Work through demand examples

Apply cuts, upgrades and sufficiency tests to complete contexts.

Worked examples · 3 problems

PROBLEM 1 · MAX-FLOW MIN-CUT THEOREM APPLIED

Network: $S \to A$ (10), $S \to B$ (7), $A \to T$ (6), $B \to T$ (9), $A \to B$ (3). (a) Calculate the capacity of all possible cuts. (b) State the minimum cut and the maximum flow. (c) Verify by applying the saturated edges method.

1
Part (a), list all possible cuts
$\{S\}|\{A,B,T\}$: $S{\to}A\ (10) + S{\to}B\ (7) = 17$
$\{S,A\}|\{B,T\}$: $S{\to}B\ (7) + A{\to}B\ (3) + A{\to}T\ (6) = 16$
$\{S,B\}|\{A,T\}$: $S{\to}A\ (10) + B{\to}T\ (9) = 19$  (note: $A{\to}B$ is backward, not counted)
$\{S,A,B\}|\{T\}$: $A{\to}T\ (6) + B{\to}T\ (9) = 15$
List every way to partition nodes into an $S$-side and $T$-side. Only count forward edges (edges pointing from $S$-side to $T$-side). Backward edges are NOT included in cut capacity.
1 of 3
PROBLEM 2 · IMPACT OF UPGRADING AN EDGE

Network: $S{\to}A$ (8), $S{\to}B$ (9), $A{\to}C$ (5), $B{\to}C$ (7), $C{\to}T$ (10). Current max flow = 10. (a) Confirm the minimum cut and max flow. (b) If $C{\to}T$ is upgraded from 10 to 14, what is the new max flow? (c) If instead $S{\to}A$ is upgraded from 8 to 15, does the max flow change?

1
Part (a), confirm min cut and max flow
$\{S\}|\text{rest}$: $8 + 9 = 17$
$\{S,A,B\}|\{C,T\}$: $A{\to}C\ (5) + B{\to}C\ (7) = 12$
$\{S,A,B,C\}|\{T\}$: $C{\to}T\ (10)$, minimum ✓
$\{S,A\}|\{B,C,T\}$: $S{\to}B\ (9) + A{\to}C\ (5) = 14$
$\{S,B\}|\{A,C,T\}$: $S{\to}A\ (8) + B{\to}C\ (7) = 15$
Minimum cut = $\{S,A,B,C\}|\{T\}$, capacity 10. Max flow = 10.
$C{\to}T$ is the only edge into $T$, so the cut just before $T$ captures all flow. Its capacity of 10 is the smallest of all cut capacities.
1 of 3
PROBLEM 3 · FULL EXAM-STYLE, SUFFICIENCY

A commuter train network has nodes $S$ (city centre), $A$, $B$, $C$ (suburbs), $T$ (airport). Edges (thousands of passengers/day): $S{\to}A$ (12), $S{\to}B$ (10), $A{\to}C$ (8), $A{\to}T$ (5), $B{\to}C$ (6), $B{\to}T$ (7), $C{\to}T$ (9). (a) Find the maximum flow. (b) Peak demand is 20 000 passengers/day. Is the network sufficient? (c) If $C{\to}T$ is upgraded from 9 to 14, is the network now sufficient? Show all working.

1
Part (a), test the candidate cuts (with three intermediate nodes there are 8 in all; these 5 are the plausible ones, and the omitted $\{S,C\}$, $\{S,A,C\}$ and $\{S,B,C\}$ come to 31, 24 and 28)
$\{S,A,B,C\}|\{T\}$: $A{\to}T\ (5) + B{\to}T\ (7) + C{\to}T\ (9) = 21$
$\{S,A,B\}|\{C,T\}$: $A{\to}C\ (8) + A{\to}T\ (5) + B{\to}C\ (6) + B{\to}T\ (7) = 26$
$\{S\}|\text{rest}$: $12 + 10 = 22$
$\{S,A\}|\{B,C,T\}$: $S{\to}B\ (10) + A{\to}C\ (8) + A{\to}T\ (5) = 23$
$\{S,B\}|\{A,C,T\}$: $S{\to}A\ (12) + B{\to}C\ (6) + B{\to}T\ (7) = 25$
Minimum cut = $\{S,A,B,C\}|\{T\}$, capacity 21. Max flow = 21 000 passengers/day.
The smallest cut capacity is 21, achieved by the cut that places all internal nodes on the $S$-side and only $T$ on the $T$-side. This cut captures the three edges entering $T$.
1 of 3

Match each scenario with its correct conclusion:

  • Max flow = 25, demand = 20
  • Max flow = 18, demand = 24
  • Upgrade a non-minimum-cut edge by 5
  • Upgrade a minimum-cut edge by 3
  • Max flow unchanged
  • Max flow increases by 3 (if no new tighter cut emerges)
  • Sufficient, 5 units per day spare capacity
  • Insufficient, shortfall of 6 units
6

Consolidate and revisit

Retrieve the decision rules and revisit the opening upgrade recommendation.

Top 3 list: List THREE steps of a complete answer when asked "Is the network sufficient to meet demand?"

09
Revisit your thinking

Pipeline: max flow 18 ML/day, demand 20 ML/day, insufficient, shortfall 2 ML/day. To upgrade ONE pipe: find the minimum cut (the cut with smallest capacity) and increase an edge in it by at least 2. Upgrading a non-minimum-cut pipe wastes money, it doesn't change max flow. If demand drops to 15 ML/day: max flow 18 ≥ 15, network is already sufficient, no upgrade needed.

auto-saved
7

Apply min-cut and demand decisions

Calculate maximum flow, assess upgrades and justify whether demand is met.

01
Short answer, exam-style questions
show all working
ApplyBand 33 marks

SA 1. A network has edges: $S{\to}A$ (9), $S{\to}B$ (7), $A{\to}T$ (6), $B{\to}T$ (8), $A{\to}B$ (2). (a) Calculate the capacity of the cut $\{S,A,B\}|\{T\}$. (b) Calculate the capacity of the cut $\{S\}|\{A,B,T\}$. (c) State the maximum flow and identify the minimum cut. (3 marks)

auto-saved
ApplyBand 3–44 marks

SA 2. A network has maximum flow of 16 units/hour and minimum cut edges $\{A{\to}T,\ B{\to}T\}$ with capacities 9 and 7. All other cuts have capacity at least 20. (a) Confirm max flow = 16. (b) Edge $A{\to}T$ is increased from 9 to 13. What is the new max flow? Explain why. (c) Instead, edge $S{\to}B$ (which is NOT in the minimum cut, capacity 10) is increased to 15. Does max flow change? Explain. (4 marks)

auto-saved
AnalyseBand 5–65 marks

SA 3. An internet service provider's data network connects a server $S$ to users at $T$ via routers $A$, $B$, $C$. Edges (Gbps): $S{\to}A$ (20), $S{\to}B$ (15), $A{\to}C$ (12), $A{\to}T$ (8), $B{\to}C$ (10), $B{\to}T$ (9), $C{\to}T$ (16). (a) Find the maximum data flow through the network. Show all cuts you evaluated. (b) Peak demand is 30 Gbps. Is the network sufficient? State the spare capacity or shortfall. (c) The provider can upgrade exactly ONE edge. Is an upgrade needed to meet peak demand? Justify your recommendation. (5 marks)

auto-saved
📖 Comprehensive answers (click to reveal)

SA 1 (3 marks): (a) $\{S,A,B\}|\{T\}$: forward edges into $T$ = $A{\to}T\ (6) + B{\to}T\ (8) = 14$. [1] (b) $\{S\}|\{A,B,T\}$: forward edges from $S$ = $S{\to}A\ (9) + S{\to}B\ (7) = 16$. [1] (c) Other cuts: $\{S,A\}|\{B,T\}$: $S{\to}B\ (7) + A{\to}B\ (2) + A{\to}T\ (6) = 15$; $\{S,B\}|\{A,T\}$: $S{\to}A\ (9) + B{\to}T\ (8) = 17$. Minimum cut = $\{S,A,B\}|\{T\}$ with capacity 14. Maximum flow = 14. [1]

SA 2 (4 marks): (a) Min cut capacity = $9 + 7 = 16$. By the max-flow min-cut theorem, max flow = 16. ✓ [1] (b) Increasing $A{\to}T$ from 9 to 13: new cut capacity $\{A{\to}T, B{\to}T\}$ = $13 + 7 = 20$. Because $A{\to}T$ lies in the original minimum cut, increasing it raises that cut capacity. Since every other cut has capacity at least 20, no smaller cut takes over and the new maximum flow is 20. [2] (c) $S{\to}B$ is NOT in the minimum cut. The minimum cut $\{A{\to}T, B{\to}T\}$ is unchanged at 16. Max flow remains 16. Changing a non-minimum-cut edge has no effect on the maximum flow. [1]

SA 3 (5 marks): (a) Key cuts evaluated: $\{S\}|\text{rest} = 20 + 15 = 35$; $\{S,A,B,C\}|\{T\} = A{\to}T\ (8) + B{\to}T\ (9) + C{\to}T\ (16) = 33$; $\{S,A,B\}|\{C,T\} = A{\to}C\ (12) + A{\to}T\ (8) + B{\to}C\ (10) + B{\to}T\ (9) = 39$; $\{S,A\}|\{B,C,T\} = S{\to}B\ (15) + A{\to}C\ (12) + A{\to}T\ (8) = 35$; $\{S,B\}|\{A,C,T\} = S{\to}A\ (20) + B{\to}C\ (10) + B{\to}T\ (9) = 39$. Minimum cut = $\{S,A,B,C\}|\{T\}$, capacity 33. Max flow = 33 Gbps. [2] (b) Max flow = 33 Gbps ≥ demand = 30 Gbps. The network IS sufficient. Spare capacity = 33 − 30 = 3 Gbps. No shortfall. [1] (c) No upgrade is required, the network already exceeds peak demand by 3 Gbps. If forced to identify an upgrade: increasing any edge in the minimum cut ($A{\to}T$, $B{\to}T$, or $C{\to}T$) would increase max flow further, but this is unnecessary. Full marks awarded for correctly identifying the network is already sufficient and stating no upgrade is needed. [2]