NSWMaths Standard 2Syllabus dot point

How is the greatest possible flow through a directed network found, and why does the smallest cut decide it?

Solve network flow problems, including finding the maximum flow using the maximum-flow minimum-cut theorem

A focused answer to the HSC Maths Standard 2 dot point on network flow. Sources and sinks, edge capacities, saturated edges, finding the maximum flow by inspection, cuts and cut capacity, the maximum-flow minimum-cut theorem, and multiple sources or sinks via a super-source and super-sink, with worked water, traffic and data examples.

Generated by Claude Opus 4.816 min answerUpdated 2026-06-21

Reviewed by: AI editorial process; not yet individually human-reviewed

Have a quick question? Jump to the Q&A page

What this dot point is asking

NESA gives you a directed network (a graph whose edges carry arrows). It has one starting vertex, the source, and one finishing vertex, the sink. Each edge has a capacity: the most it can carry. Your job is to find the maximum flow, the greatest amount that can pass from source to sink at once. You confirm that maximum using cuts and the maximum-flow minimum-cut theorem. If a network has more than one source or sink, you add a super-source and super-sink.

The capacity can be anything that moves through a one-way channel: water in kilolitres per minute through pipes, cars per hour along one-way roads, or data in megabits per second across links. The method is identical in each case; only the units change.

The answer

The vocabulary you must use

A flow network is a directed graph (the edges carry arrows), so flow only travels the way the arrow points. The pieces have precise names, and exam questions expect them:

Source. The single vertex where everything starts. Here it is $S$ . The source is the analogue of the "start" in critical path analysis.
Sink. The single vertex where everything ends. Here it is $T$ , the analogue of the "finish".
Capacity. The weight on an edge: the most that edge can carry. Pipe $S$ - $A$ has capacity $12$ , meaning at most $12$ kilolitres per minute can pass along it.
Flow. The amount actually travelling along an edge. The flow on an edge can be anything from $0$ up to its capacity, never more.
Saturated edge. An edge whose flow equals its capacity. It is full and cannot carry any more, so it is a candidate bottleneck.
Excess (spare) capacity. Capacity minus current flow: the room still left on an edge. This is the flow-network cousin of float time in critical path analysis.

The single most important fact is the first rule of capacity: the flow on any edge can never exceed that edge's capacity. Everything that follows is a consequence of squeezing flow through edges that each have a ceiling.

Flow must be conserved at every vertex

At every vertex except the source and the sink, whatever flows in must flow out. Water does not pile up at a junction or appear from nowhere. So if $9$ kilolitres per minute arrive at vertex $C$ , then $9$ must leave $C$ . This is conservation of flow, and it is why a single narrow edge anywhere along a route throttles the whole route: the flow that squeezes through the narrow edge is all that can continue past it.

Finding the maximum flow by inspection

For a small network you can find the maximum flow by eye, building it from paths:

Trace a path from source to sink and read off its bottleneck. The flow you can push along a single path is the smallest capacity on it (the series rule). Send that much, and mark each edge on the path as carrying that flow.
Reduce the capacities you have used. Subtract the flow you just sent from every edge on that path. Some edge becomes saturated (drops to $0$ spare); that is the bottleneck that limited the path.
Find another path that still has spare capacity and repeat, adding its flow to the running total.
Stop when no path from source to sink has spare capacity left. The running total is the maximum flow.

Step 2 is the part that trips students, and textbooks gloss over it. If two paths share an edge, you cannot just add their separate bottlenecks. The shared edge can only carry its own capacity in total. So you must subtract used capacity as you go, which stops a shared edge from being over-committed (asked to carry more than it can). The traffic worked example below is built to expose this trap.

Cuts: a cleaner way to pin the maximum

On a bigger network, inspection becomes error-prone: it is hard to be sure you have not missed a better combination of paths. Cuts give a check that does not rely on finding the right paths.

A cut is an imaginary line drawn right across the network. It completely separates the source from the sink, so every route from source to sink is cut. Think of it as a set of pipes you could close to stop all flow getting through. Because a cut blocks every route, the flow can never beat the total capacity of the pipes it crosses. That fact leads straight to the theorem.

The capacity of a cut is the sum of the capacities of the edges crossing it, but only those running from the source side to the sink side. This direction rule is the part most often got wrong:

An edge pointing from the source side to the sink side is counted: flow uses it to cross, so it limits the cut.
An edge pointing from the sink side back to the source side is not counted: it carries flow the wrong way across the cut, so it does not help flow get from source to sink and is ignored entirely.

In the cut shown, the dashed line puts $S$ , $A$ and $B$ on the source side and $C$ , $D$ , $T$ on the sink side. The three pipes crossing it from source side to sink side are $A$ - $C$ ( $7$ ), $B$ - $C$ ( $5$ ) and $B$ - $D$ ( $6$ ), so the cut capacity is $7 + 5 + 6 = 18$ . Notice it does not count $S$ - $A$ , $S$ - $B$ or the internal pipe $A$ - $B$ , because those stay entirely on the source side and never cross the line.

The maximum-flow minimum-cut theorem

Every cut is a complete barrier, so the flow can never beat the capacity of any single cut. The tightest barrier, the minimum cut, is therefore the true ceiling, and the theorem says that ceiling is always reached.

In our network the minimum cut is the one drawn above, with capacity $18$ , so the maximum flow from $S$ to $T$ is $18$ kilolitres per minute. The bottleneck is the middle layer of pipes, not the source pipes (which together carry $12 + 14 = 26$ ) nor the pipes into the sink (which carry $13 + 10 = 23$ ). That is the lesson the theorem makes vivid: the constriction can sit anywhere in the network, and the minimum cut finds it for you.

Why the two numbers must agree

You can see why a flow can never beat a cut without any algebra. Picture any cut as a line across all the pipes. Every drop that reaches the sink had to start at the source. So it had to cross that line somewhere, along a source-to-sink pipe. The total crossing the line can therefore be no more than the total capacity of those pipes, which is the cut capacity. This holds for every cut, so the flow is at most the smallest cut. The theorem also claims you can always set up a flow that exactly equals the smallest cut, so the two values meet. In Standard 2 you use the result, not its proof, but the picture is what makes it clear.

Multiple sources or multiple sinks

Some networks have more than one source (say two reservoirs feeding a town) or more than one sink (say two ocean outlets). The trick is to reduce the problem to the single-source single-sink case you already know:

Add one super-source: a new vertex joined by an edge to every real source.
Add one super-sink: a new vertex joined by an edge from every real sink.
Give each artificial edge a capacity at least as large as everything that source can emit or that sink can receive (a safe choice is the sum of the real pipes at that vertex), so the artificial edges never become the bottleneck themselves.

Now find the maximum flow from the super-source to the super-sink exactly as before. Because the artificial edges are never the constriction, the answer is the genuine maximum total flow through the original network. The stormwater worked example below carries this out in full.

How exam questions ask about network flow

The wording shifts with the context, but each version maps onto the same toolkit. Learn to translate it:

"Find the maximum flow from $S$ to $T$ ." Either build it up by inspection (paths, bottlenecks, subtracting used capacity) or, more reliably, find the minimum cut and quote the theorem. State the value with units.
"Find the capacity of cut $C_1$ / each of the cuts shown." Sum the capacities of the edges crossing in the source-to-sink direction only; ignore any edge crossing the other way.
"Use the maximum-flow minimum-cut theorem" or "verify your answer with a cut." They want both: a flow that achieves a value, and a cut of the same capacity confirming nothing larger is possible.
"Which edges are saturated at maximum flow?" Name the edges whose flow equals their capacity. The saturated edges of a minimum cut are exactly the bottleneck.
"A pipe / road is upgraded (or closed)." Change that one capacity, then re-find the minimum cut. Upgrading a pipe that is not on the minimum cut changes nothing; only relieving the bottleneck raises the maximum flow.
"There are two sources / two sinks." Add a super-source and super-sink, then solve the single-source single-sink problem.
"Find one example of how the maximum flow can be achieved." Give an actual flow on each edge (not just the total) that sums to the maximum and never exceeds any capacity.

A distinction worth a mark: maximum flow is about pushing the most through a directed network from one vertex to another, and is not the same as a minimum spanning tree (connect every vertex as cheaply as possible) or a shortest path (the single cheapest route between two vertices). Read the directed arrows and the word "capacity" as your signal that it is a flow problem.

Worked example

Maximum flow through pipes in series and in parallel

A small irrigation system carries water in kilolitres per minute. First consider one straight run, then two independent runs.

Set up the series case: Water flows source $S$ to $A$ to sink $T$ . Pipe $S$ - $A$ has capacity $25$ and pipe $A$ - $T$ has capacity $58$ . These pipes are joined in series (one after the other on a single path).
Apply the bottleneck rule: Flow on a series path is limited by the smallest capacity on it. The smaller of $25$ and $58$ is $25$ , so at most $25$ can flow. The wide pipe $A$ - $T$ runs below its capacity: it carries the $25$ that the narrow pipe lets through and has $58 - 25 = 33$ kilolitres per minute of spare capacity. The narrow pipe $S$ - $A$ is saturated.
Answer (series): the maximum flow is $25$ kilolitres per minute, set by the narrowest pipe.
Now set up the parallel case: Add a second, separate route. Route 1 is $S$ - $A$ - $T$ with capacities $40$ then $30$ . Route 2 is $S$ - $B$ - $T$ with capacities $20$ then $35$ . The two routes share no edge.
Find each route's bottleneck, then add: Route 1 is limited by $\min(40, 30) = 30$ . Route 2 is limited by $\min(20, 35) = 20$ . Because the routes are independent (no shared pipe), their flows add: $30 + 20 = 50$ .
Answer (parallel): the maximum flow is $30 + 20 = 50$ kilolitres per minute. Adding the route bottlenecks is valid here only because no edge is shared, the condition the next example removes.

Maximum traffic flow through a shared road

A one-way road network carries cars per hour. The source is $A$ and the sink is $E$ . The roads are $A$ - $B$ ( $300$ ), $B$ - $C$ ( $600$ ), $A$ - $D$ ( $500$ ), $D$ - $C$ ( $150$ ) and the final shared road $C$ - $E$ ( $400$ ). Both routes to $E$ run through $C$ and then down the single road $C$ - $E$ . Find the maximum traffic flow from $A$ to $E$ .

Read the two routes and their bottlenecks: Route 1 is $A$ - $B$ - $C$ - $E$ with bottleneck $\min(300, 600, 400) = 300$ . Route 2 is $A$ - $D$ - $C$ - $E$ with bottleneck $\min(500, 150, 400) = 150$ . Naively adding these gives $300 + 150 = 450$ .
Spot the shared edge and correct: Both routes funnel through the single road $C$ - $E$ , which has capacity only $400$ . The proposed $450$ would force $450$ cars per hour down a road that holds $400$ , which is impossible. So $C$ - $E$ is the bottleneck for the combined flow, not the individual routes. This is exactly the trap: route bottlenecks may not be added when an edge is shared.
Confirm with a cut: Put $C$ , $E$ on the sink side and everything else on the source side. The only edge crossing source-to-sink is $C$ - $E$ , capacity $400$ , so this cut has capacity $400$ . No cut can be smaller than the single road every car must use, so by the maximum-flow minimum-cut theorem the maximum flow is $400$ .
Answer: the maximum traffic flow from $A$ to $E$ is $400$ cars per hour, limited by the shared road $C$ - $E$ . A valid split is $300$ cars per hour via $B$ and $100$ via $D$ , totalling $400$ and respecting every capacity.

Cut capacities and the minimum cut on a data network

A data centre streams from server $S$ to client $T$ across one-way links measured in megabits per second: $S$ - $A$ ( $10$ ), $S$ - $B$ ( $8$ ), $A$ - $C$ ( $6$ ), $B$ - $A$ ( $4$ ), $B$ - $D$ ( $9$ ), $C$ - $T$ ( $7$ ), $D$ - $T$ ( $5$ ) and a cross-link $C$ - $D$ ( $3$ ). Note the link $B$ - $A$ points from $B$ to $A$ . Find the maximum flow from $S$ to $T$ by computing cut capacities.

Compute a cut with a back-pointing edge: Take the cut with source side $\{S, A\}$ and sink side $\{B, C, D, T\}$ . The edges crossing source-to-sink are $S$ - $B$ ( $8$ ) and $A$ - $C$ ( $6$ ). The link $B$ - $A$ crosses the other way (sink side to source side), so it is not counted. Cut capacity $= 8 + 6 = 14$ .
Compute a few more cuts: Source side $\{S, A, B\}$ : crossings $A$ - $C$ ( $6$ ) and $B$ - $D$ ( $9$ ), capacity $6 + 9 = 15$ . Source side $\{S, A, B, C, D\}$ (everything but the sink): crossings $C$ - $T$ ( $7$ ) and $D$ - $T$ ( $5$ ), capacity $7 + 5 = 12$ . Source side $\{S, A, B, D\}$ : crossings $A$ - $C$ ( $6$ ) and $D$ - $T$ ( $5$ ), capacity $6 + 5 = 11$ .
Take the minimum: The smallest cut capacity found is $11$ , from the cut $\{S, A, B, D\}$ versus $\{C, T\}$ , crossing $A$ - $C$ and $D$ - $T$ . No combination of paths can beat the tightest barrier.
Answer: by the maximum-flow minimum-cut theorem the maximum flow from $S$ to $T$ is $11$ megabits per second. The bottleneck links $A$ - $C$ ( $6$ ) and $D$ - $T$ ( $5$ ) are saturated when the flow is at its maximum.

Maximum stormwater flow with two sources and two sinks

Storm water enters at Dunlop North ( $P$ ) and Dunlop South ( $Q$ ) and drains to the ocean at Outlet 1 ( $Y$ ) and Outlet 2 ( $Z$ ), through junctions $R$ and $S$ . Capacities in kilolitres per minute are $P$ - $R$ ( $8$ ), $P$ - $S$ ( $6$ ), $Q$ - $S$ ( $9$ ), $Q$ - $R$ ( $4$ ), $R$ - $Y$ ( $7$ ), $R$ - $Z$ ( $5$ ), $S$ - $Y$ ( $3$ ) and $S$ - $Z$ ( $10$ ). Find the maximum total rate at which water leaves the network.

Add a super-source and super-sink: There are two sources and two sinks, so introduce a super-source $X$ feeding both $P$ and $Q$ , and a super-sink $W$ fed from both $Y$ and $Z$ . Give each artificial pipe the total capacity at that vertex so it is never the bottleneck: $X$ - $P = 8 + 6 = 14$ , $X$ - $Q = 9 + 4 = 13$ , $Y$ - $W = 7 + 3 = 10$ and $Z$ - $W = 5 + 10 = 15$ . The problem is now a single source $X$ to a single sink $W$ .
Test the cut just before the outlets: Put everything except $Y$ , $Z$ , $W$ on the source side. The crossing edges are the four pipes feeding the outlets: $R$ - $Y$ ( $7$ ), $R$ - $Z$ ( $5$ ), $S$ - $Y$ ( $3$ ) and $S$ - $Z$ ( $10$ ). Cut capacity $= 7 + 5 + 3 + 10 = 25$ .
Test the cut just after the sources: Put only $X$ , $P$ , $Q$ on the source side. The crossing edges are the four pipes leaving the sources: $P$ - $R$ ( $8$ ), $P$ - $S$ ( $6$ ), $Q$ - $S$ ( $9$ ) and $Q$ - $R$ ( $4$ ). Cut capacity $= 8 + 6 + 9 + 4 = 27$ .
Take the minimum and read the answer: The smaller of these is $25$ , and checking shows no cut is smaller, so the minimum cut is $25$ . By the maximum-flow minimum-cut theorem the maximum total flow is $25$ kilolitres per minute. The bottleneck is the set of pipes feeding the ocean outlets ( $25$ ), not the pipes leaving the suburbs ( $27$ ).
Answer: the maximum total rate water can leave the network is $25$ kilolitres per minute. The artificial super-source and super-sink let two sources and two sinks be solved as one ordinary flow problem.

Common traps

Adding route bottlenecks when an edge is shared: Two routes through the same pipe cannot each send their full bottleneck; the shared edge caps their combined flow. Subtract used capacity as you go, or find the minimum cut.
Counting a cut edge that points the wrong way: A cut's capacity sums only the edges crossing from the source side to the sink side. An edge crossing back the other way is ignored, not subtracted.
Stopping at the first cut you draw: The theorem uses the cut of least capacity. Test several cuts and take the minimum; the bottleneck is often in the middle, not at the source or the sink.
Ignoring the arrows: Flow networks are directed. Flow can only travel the way an arrow points, so a one-way pipe never carries flow backwards.
Forgetting conservation of flow: Flow in must equal flow out at every vertex except the source and sink. A junction cannot store or create flow.
Leaving a multi-source or multi-sink problem un-reduced: Add a super-source and a super-sink first, with artificial capacities large enough that they are never the bottleneck, then solve as a single source to a single sink.

Exam technique

Lead with the minimum cut: it is the most reliable way to nail the maximum flow and earns the method marks. Draw a candidate cut line, list the edges it crosses, and add only the source-to-sink crossings (watch for any edge pointing the wrong way, which you ignore). Test several cuts and quote the smallest, then write one line invoking the theorem: "the maximum flow equals the minimum cut, so the answer is ...". Always state the value with units (kilolitres per minute, cars per hour, megabits per second). If the question says "verify", give a flow that achieves the value as well as the matching cut. For two sources or two sinks, set up a super-source and super-sink before doing anything else. And before you start, confirm it is a flow problem (directed edges, capacities) and not a shortest path or minimum spanning tree.

Exam-style practice questions

Practice questions written in the style of NESA exam questions on this dot point, with worked answer explainers. The year tag is the paper they imitate, not the source.

2022 HSC-style4 marksWater flows through a network of pipes from source

S

to sink

T

. The capacities, in kilolitres per minute, are

S

A

14

S

B

10

A

C

9

A

B

5

B

C

8

C

T

12

B

T

6

. All pipes are one-way from

S

towards

T

. Find the maximum flow from

S

T

, justifying your answer with a cut.

Show worked answer →

Find the maximum flow by locating the minimum cut. A cut is an imaginary line that completely separates $S$ from $T$ ; its capacity is the sum of the capacities of the edges crossing it in the source-to-sink direction only.

Test cuts that separate more and more of the network from the sink:

Cut $\{S\}$ on the source side: crossings $S$ - $A$ and $S$ - $B$ , capacity $14 + 10 = 24$ .
Cut $\{S, A\}$ : crossings $S$ - $B$ , $A$ - $C$ , $A$ - $B$ , capacity $10 + 9 + 5 = 24$ .
Cut $\{S, A, B\}$ : crossings $A$ - $C$ , $B$ - $C$ , $B$ - $T$ , capacity $9 + 8 + 6 = 23$ .
Cut $\{S, A, B, C\}$ : crossings $C$ - $T$ , $B$ - $T$ , capacity $12 + 6 = 18$ .

The smallest cut capacity is $18$ , so by the maximum-flow minimum-cut theorem the maximum flow is $18$ kilolitres per minute. The bottleneck is the pair of pipes feeding $T$ .

Markers reward identifying several cuts, summing only the source-to-sink crossings, choosing the minimum, and quoting the theorem to convert the minimum cut into the maximum flow, with units.

2023 HSC-style5 marksStorm water enters a pipe network at Dunlop North (

M

) or Dunlop South (

N

) and leaves at Outlet 1 (

G

) or Outlet 2 (

H

). Capacities in kilolitres per minute are

M

U

6

M

V

9

N

U

7

N

V

4

U

G

8

U

H

3

V

G

5

V

H

11

. Find the maximum total rate at which water can leave the network at the two outlets.

Show worked answer →

There are two sources and two sinks, so add a super-source $X$ joined to both real sources and a super-sink $W$ joined from both real sinks. Give each artificial pipe a capacity equal to the total capacity of the pipes at that source or sink, so the artificial pipes never become the bottleneck: $X$ - $M = 6 + 9 = 15$ , $X$ - $N = 7 + 4 = 11$ , $G$ - $W = 8 + 5 = 13$ , $H$ - $W = 3 + 11 = 14$ .

Now it is a single-source single-sink problem from $X$ to $W$ . Find the minimum cut. The maximum flow works out to $24$ kilolitres per minute, and a cut achieving it crosses $M$ - $V$ $9$ , $N$ - $V$ $4$ , $U$ - $G$ $8$ and $U$ - $H$ $3$ , which sum to $9 + 4 + 8 + 3 = 24$ .

Markers reward the super-source and super-sink construction, reducing two sources and two sinks to one of each, finding the maximum flow with a confirming cut, and stating the total rate with units.

Practice questions

Original practice questions graded from foundation to exam level, each with a full worked solution. Try them before revealing the solution.

foundation2 marksWater flows in kilolitres per minute through two pipes joined in series: source

S

to junction

A

with capacity

18

, then

A

to sink

T

with capacity

27

. Every pipe is one-way from

S

towards

T

. Find the maximum flow from

S

T

Show worked solution →

Read the path: There is one route, $S$ to $A$ to $T$ , with the two pipes joined in series (one after the other).
Apply the bottleneck (series) rule: Flow on a series path is limited by its smallest capacity. The smaller of $18$ and $27$ is $\min(18, 27) = 18$ , so at most $18$ can pass. The wide pipe $A$ - $T$ then carries only $18$ and has $27 - 18 = 9$ kilolitres per minute of spare capacity, while $S$ - $A$ is saturated.
Confirm with a cut: Put just $S$ on the source side. The only pipe crossing source-to-sink is $S$ - $A$ , so the cut capacity is $18$ . No cut can be smaller than the single pipe leaving $S$ , so by the maximum-flow minimum-cut theorem the maximum flow is $18$ .
Check: The flow $18$ equals the cut $18$ , and $18 \le 18$ and $18 \le 27$ respect both capacities. The maximum flow is $18$ kilolitres per minute.

foundation2 marksA network carries cars per hour along one-way roads from source

S

to sink

E

by two separate routes that share no road. Route 1 is

S

A

E

with capacities

16

then

9

. Route 2 is

S

B

E

with capacities

11

then

20

. Find the maximum traffic flow from

S

E

Show worked solution →

Find each route's bottleneck: On a series route the flow is capped by the smallest capacity. Route 1 is limited by $\min(16, 9) = 9$ . Route 2 is limited by $\min(11, 20) = 11$ .
Add the routes: The two routes share no road, so their flows are independent and add: $9 + 11 = 20$ cars per hour.
Confirm with a cut: Take the source side $\{S, A\}$ . The pipes crossing source-to-sink are $A$ - $E$ ( $9$ ) and $S$ - $B$ ( $11$ ), giving cut capacity $9 + 11 = 20$ . This matches the flow, so by the maximum-flow minimum-cut theorem $20$ is the maximum.
Check: Flow $20$ equals the cut $20$ ; sending $9$ via $A$ and $11$ via $B$ breaks no capacity. The maximum flow is $20$ cars per hour.

foundation3 marksWater flows in kilolitres per minute through one-way pipes from source

S

to sink

T

S

A

13

S

B

7

A

T

10

B

T

12

. (a) Find the capacity of the cut that puts only

S

on the source side. (b) Find the maximum flow from

S

T

, justifying it with a cut.

Show worked solution →

(a) Cut around the source. With only $S$ on the source side, the pipes crossing source-to-sink are $S$ - $A$ ( $13$ ) and $S$ - $B$ ( $7$ ). The cut capacity is $13 + 7 = 20$ .

(b) Test more cuts. A cut is a line separating $S$ from $T$ ; sum only the source-to-sink crossings.

Source side $\{S\}$ : crossings $S$ - $A$ , $S$ - $B$ , capacity $13 + 7 = 20$ .
Source side $\{S, A\}$ : crossings $S$ - $B$ ( $7$ ), $A$ - $T$ ( $10$ ), capacity $7 + 10 = 17$ .
Source side $\{S, B\}$ : crossings $S$ - $A$ ( $13$ ), $B$ - $T$ ( $12$ ), capacity $13 + 12 = 25$ .
Source side $\{S, A, B\}$ : crossings $A$ - $T$ ( $10$ ), $B$ - $T$ ( $12$ ), capacity $10 + 12 = 22$ .

Take the minimum. The smallest is $17$ , so by the maximum-flow minimum-cut theorem the maximum flow is $17$ kilolitres per minute.

Check. A flow of $10$ along $S$ - $A$ - $T$ and $7$ along $S$ - $B$ - $T$ totals $17$ and breaks no capacity, matching the minimum cut $17$ .

foundation3 marksA water network has one-way pipes measured in kilolitres per minute:

S

A

8

S

B

6

A

C

5

B

C

9

C

T

7

. Every route from source

S

to sink

T

passes through the single pipe

C

T

. Find the maximum flow from

S

T

Show worked solution →

Spot the shared final pipe: Both routes ( $S$ - $A$ - $C$ - $T$ and $S$ - $B$ - $C$ - $T$ ) funnel through the one pipe $C$ - $T$ , which has capacity only $7$ . No flow can pass $C$ to $T$ faster than $7$ .
Confirm with a cut: Put $C$ and $T$ on the sink side and $S$ , $A$ , $B$ on the source side. The only pipe crossing source-to-sink is $C$ - $T$ ( $7$ ), so the cut capacity is $7$ . No cut can be smaller than the single pipe every drop must use.
Read the theorem: By the maximum-flow minimum-cut theorem the maximum flow equals this minimum cut, so it is $7$ kilolitres per minute. Upstream the network is wider (the pipes into $C$ carry $5 + 9 = 14$ ), but $C$ - $T$ throttles everything.
Check: A flow of $5$ via $A$ and $2$ via $B$ gives $5 + 2 = 7$ into $C$ and $7$ out along $C$ - $T$ , respecting every capacity and matching the cut $7$ .

core4 marksA pipe network carries water in kilolitres per minute with one-way pipes

S

A

10

S

B

9

A

B

4

A

T

7

B

T

11

. Note the internal pipe

A

B

runs from

A

B

. Find the maximum flow from

S

T

, justifying it with a cut.

Show worked solution →

Test the cut into the sink. Put $S$ , $A$ , $B$ on the source side and only $T$ on the sink side. The crossings are $A$ - $T$ ( $7$ ) and $B$ - $T$ ( $11$ ), so this cut has capacity $7 + 11 = 18$ .

Check it is the minimum. Compare other cuts so $18$ is not beaten:

Source side $\{S\}$ : crossings $S$ - $A$ ( $10$ ), $S$ - $B$ ( $9$ ), capacity $10 + 9 = 19$ .
Source side $\{S, A\}$ : crossings $S$ - $B$ ( $9$ ), $A$ - $B$ ( $4$ ), $A$ - $T$ ( $7$ ), capacity $9 + 4 + 7 = 20$ .
Source side $\{S, B\}$ : crossings $S$ - $A$ ( $10$ ), $B$ - $T$ ( $11$ ), capacity $10 + 11 = 21$ .

The smallest is $18$ .

Read the theorem. By the maximum-flow minimum-cut theorem the maximum flow is $18$ kilolitres per minute.

Check with an actual flow. Send $S$ - $A$ $9$ , $S$ - $B$ $9$ , $A$ - $B$ $2$ , $A$ - $T$ $7$ , $B$ - $T$ $11$ . Vertex $A$ takes in $9$ and sends out $2 + 7 = 9$ ; vertex $B$ takes in $9 + 2 = 11$ and sends out $11$ . The total into $T$ is $7 + 11 = 18$ , matching the cut.

core4 marksData flows in megabits per second across one-way links

S

A

12

S

B

8

A

C

10

B

D

7

C

D

3

C

T

6

D

T

9

. Find the maximum flow from source

S

to sink

T

, and name the links that are saturated when the flow is at its maximum.

Show worked solution →

Test the cut into the sink. Put everything except $T$ on the source side. The crossings are $C$ - $T$ ( $6$ ) and $D$ - $T$ ( $9$ ), so this cut has capacity $6 + 9 = 15$ .

Check it is the minimum. Try other cuts:

Source side $\{S\}$ : crossings $S$ - $A$ ( $12$ ), $S$ - $B$ ( $8$ ), capacity $12 + 8 = 20$ .
Source side $\{S, A\}$ : crossings $S$ - $B$ ( $8$ ), $A$ - $C$ ( $10$ ), capacity $8 + 10 = 18$ .

Neither beats $15$ , so the minimum cut is $15$ .

Read the theorem: By the maximum-flow minimum-cut theorem the maximum flow is $15$ megabits per second.
Find a flow and its saturated links: Send $S$ - $A$ $8$ , $S$ - $B$ $7$ , $A$ - $C$ $8$ , $C$ - $T$ $6$ , $C$ - $D$ $2$ , $B$ - $D$ $7$ , $D$ - $T$ $9$ . Conservation holds at every junction, and the total into $T$ is $6 + 9 = 15$ . The links carrying their full capacity are $C$ - $T$ ( $6 = 6$ ) and $D$ - $T$ ( $9 = 9$ ), which are exactly the minimum-cut bottleneck.
Check: Flow $15$ equals cut $15$ , confirming the answer; the saturated links are $C$ - $T$ and $D$ - $T$ .

core4 marksCars per hour travel one-way roads

S

A

9

S

B

11

A

C

7

A

D

4

B

D

8

C

T

6

D

T

10

from source

S

to sink

T

. Find the maximum traffic flow from

S

T

by computing cut capacities.

Show worked solution →

Test several cuts. Sum only the source-to-sink crossings.

Source side $\{S\}$ : crossings $S$ - $A$ ( $9$ ), $S$ - $B$ ( $11$ ), capacity $9 + 11 = 20$ .
Source side $\{S, A, B\}$ : crossings $A$ - $C$ ( $7$ ), $A$ - $D$ ( $4$ ), $B$ - $D$ ( $8$ ), capacity $7 + 4 + 8 = 19$ .
Source side $\{S, A, B, C, D\}$ (all but the sink): crossings $C$ - $T$ ( $6$ ), $D$ - $T$ ( $10$ ), capacity $6 + 10 = 16$ .

Take the minimum: The smallest cut found is $16$ , the pair of roads feeding $T$ .
Read the theorem: By the maximum-flow minimum-cut theorem the maximum flow is $16$ cars per hour.
Check with an actual flow: Send $S$ - $A$ $9$ , $S$ - $B$ $7$ , $A$ - $C$ $6$ , $A$ - $D$ $3$ , $B$ - $D$ $7$ , $C$ - $T$ $6$ , $D$ - $T$ $10$ . At $A$ : in $9$ , out $6 + 3 = 9$ . At $D$ : in $3 + 7 = 10$ , out $10$ . The total into $T$ is $6 + 10 = 16$ , matching the minimum cut $16$ .

core5 marksWater flows in kilolitres per minute through one-way pipes

S

A

10

S

B

6

A

C

7

B

C

9

C

T

8

from source

S

to sink

T

. (a) Find the maximum flow. (b) The council upgrades pipe

C

T

to capacity

15

. Find the new maximum flow. (c) Explain why the increase is not the full amount

C

T

was widened.

Show worked solution →

(a) Find the original minimum cut: Put $S$ , $A$ , $B$ , $C$ on the source side. The only crossing is $C$ - $T$ ( $8$ ), so that cut is $8$ . The cut $\{S\}$ gives $S$ - $A$ ( $10$ ) plus $S$ - $B$ ( $6$ ) $= 16$ , and $\{S, A, B\}$ gives $A$ - $C$ ( $7$ ) plus $B$ - $C$ ( $9$ ) $= 16$ , both larger. The minimum is $8$ , so the maximum flow is $8$ kilolitres per minute.
(b) Re-find the minimum cut after the upgrade: Now $C$ - $T$ has capacity $15$ , so the cut $\{S, A, B, C\}$ is $15$ . The other cuts are unchanged: $\{S\}$ is $16$ , and the cut $\{S, A\}$ gives $S$ - $B$ ( $6$ ) plus $A$ - $C$ ( $7$ ) $= 13$ . The new minimum is $13$ , so the new maximum flow is $13$ kilolitres per minute.
(c) Explain the size of the gain: Widening $C$ - $T$ from $8$ to $15$ moved the bottleneck off that pipe and onto the pipes feeding $A$ and on into $C$ : the cut $\{S, A\}$ , crossing $S$ - $B$ ( $6$ ) and $A$ - $C$ ( $7$ ), now caps the flow at $13$ . The flow rose by only $13 - 8 = 5$ , not $15 - 8 = 7$ , because once a different cut becomes the minimum, further widening of $C$ - $T$ adds nothing.
Check: A flow of $S$ - $A$ $7$ , $S$ - $B$ $6$ , $A$ - $C$ $7$ , $B$ - $C$ $6$ , $C$ - $T$ $13$ gives $7 + 6 = 13$ into $C$ and $13$ out, matching the new minimum cut $13$ .

exam5 marksData flows in megabits per second across one-way links

S

A

11

S

B

9

B

A

4

A

C

8

B

D

7

C

D

3

C

T

6

D

T

10

. Note the link

B

A

points from

B

A

. (a) Find the capacity of the cut with source side

\{S, A\}

. (b) Find the maximum flow from

S

T

Show worked solution →

(a) Apply the direction rule. With source side $\{S, A\}$ and sink side $\{B, C, D, T\}$ , the links crossing source-to-sink are $S$ - $B$ ( $9$ ) and $A$ - $C$ ( $8$ ). The link $B$ - $A$ crosses the other way (sink side to source side), so it is not counted. The cut capacity is $9 + 8 = 17$ .

(b) Test more cuts. Sum only the source-to-sink crossings.

Source side $\{S, A, B\}$ : crossings $A$ - $C$ ( $8$ ), $B$ - $D$ ( $7$ ), capacity $8 + 7 = 15$ .
Source side $\{S, A, B, D\}$ : crossings $A$ - $C$ ( $8$ ), $D$ - $T$ ( $10$ ), capacity $8 + 10 = 18$ .
Source side $\{S, A, B, C, D\}$ : crossings $C$ - $T$ ( $6$ ), $D$ - $T$ ( $10$ ), capacity $6 + 10 = 16$ .

Take the minimum: The smallest is $15$ , from $\{S, A, B\}$ .
Read the theorem: By the maximum-flow minimum-cut theorem the maximum flow is $15$ megabits per second.
Check: A flow of $S$ - $A$ $8$ , $S$ - $B$ $7$ , $A$ - $C$ $8$ , $B$ - $D$ $7$ , $C$ - $T$ $6$ , $C$ - $D$ $2$ , $D$ - $T$ $9$ sends $6 + 9 = 15$ into $T$ and obeys every capacity, matching the cut $15$ .

exam6 marksStorm water enters at Dunlop North (

P

) and Dunlop South (

Q

) and drains to the ocean at Outlet 1 (

Y

) and Outlet 2 (

Z

) through junctions

R

and

S

. Capacities in kilolitres per minute are

P

R

9

P

S

5

Q

S

8

Q

R

6

R

Y

7

R

Z

4

S

Y

3

S

Z

11

. Find the maximum total rate at which water leaves the network.

Show worked solution →

Add a super-source and super-sink: Two sources and two sinks reduce to one of each. Add super-source $X$ feeding $P$ and $Q$ , and super-sink $W$ fed from $Y$ and $Z$ . Give each artificial pipe the total capacity at that vertex so it is never the bottleneck: $X$ - $P = 9 + 5 = 14$ , $X$ - $Q = 8 + 6 = 14$ , $Y$ - $W = 7 + 3 = 10$ , $Z$ - $W = 4 + 11 = 15$ .
Test the cut just before the outlets: Put everything except $Y$ , $Z$ , $W$ on the source side. Crossings $R$ - $Y$ ( $7$ ), $R$ - $Z$ ( $4$ ), $S$ - $Y$ ( $3$ ), $S$ - $Z$ ( $11$ ) give $7 + 4 + 3 + 11 = 25$ .
Test a mixed cut: Put $X$ , $P$ , $Q$ , $R$ on the source side. The crossings are $P$ - $S$ ( $5$ ), $Q$ - $S$ ( $8$ ), $R$ - $Y$ ( $7$ ) and $R$ - $Z$ ( $4$ ), giving $5 + 8 + 7 + 4 = 24$ . Note $Q$ - $R$ and $P$ - $R$ stay inside the source side and are not counted.
Take the minimum: The smaller is $24$ , and no cut is smaller, so the minimum cut is $24$ . By the maximum-flow minimum-cut theorem the maximum total flow is $24$ kilolitres per minute.
Check: A flow with $P$ - $R$ $5$ , $P$ - $S$ $5$ , $Q$ - $R$ $6$ , $Q$ - $S$ $8$ , $R$ - $Y$ $7$ , $R$ - $Z$ $4$ , $S$ - $Y$ $3$ , $S$ - $Z$ $10$ delivers $10$ to $Y$ and $14$ to $Z$ , a total of $24$ leaving the network, matching the minimum cut.

exam6 marksWater flows in kilolitres per minute through one-way pipes

S

A

14

S

B

10

A

C

9

A

D

5

B

D

8

C

D

3

C

T

11

D

T

9

from source

S

to sink

T

. By testing several cuts, find the maximum flow from

S

T

and state the minimum cut that achieves it.

Show worked solution →

Test cuts that move more of the network to the sink side. Sum only the source-to-sink crossings.

Source side $\{S\}$ : crossings $S$ - $A$ ( $14$ ), $S$ - $B$ ( $10$ ), capacity $14 + 10 = 24$ .
Source side $\{S, A, B\}$ : crossings $A$ - $C$ ( $9$ ), $A$ - $D$ ( $5$ ), $B$ - $D$ ( $8$ ), capacity $9 + 5 + 8 = 22$ .
Source side $\{S, A, B, C, D\}$ (all but the sink): crossings $C$ - $T$ ( $11$ ), $D$ - $T$ ( $9$ ), capacity $11 + 9 = 20$ .
Source side $\{S, A, B, D\}$ : crossings $A$ - $C$ ( $9$ ), $D$ - $T$ ( $9$ ), capacity $9 + 9 = 18$ .

Take the minimum: The smallest is $18$ , from the cut $\{S, A, B, D\}$ versus $\{C, T\}$ , crossing $A$ - $C$ ( $9$ ) and $D$ - $T$ ( $9$ ). Note $C$ - $D$ runs from the sink side back to the source side, so it is not counted.
Read the theorem: By the maximum-flow minimum-cut theorem the maximum flow is $18$ kilolitres per minute.
Check: A flow of $S$ - $A$ $14$ , $S$ - $B$ $4$ , $A$ - $C$ $9$ , $A$ - $D$ $5$ , $B$ - $D$ $4$ , $C$ - $T$ $9$ , $D$ - $T$ $9$ sends $9 + 9 = 18$ into $T$ and obeys every capacity, matching the minimum cut $18$ .

exam7 marksCars per hour travel one-way roads

S

A

13

S

B

11

A

C

8

A

D

6

B

D

9

B

E

4

C

T

10

D

T

7

E

T

12

from source

S

to sink

T

. (a) Find the maximum flow from

S

T

. (b) State a minimum cut whose capacity equals it. (c) Give one example of a flow on each road that achieves the maximum.

Show worked solution →

(a) Test cuts to locate the bottleneck. Sum only the source-to-sink crossings.

Source side $\{S\}$ : crossings $S$ - $A$ ( $13$ ), $S$ - $B$ ( $11$ ), capacity $13 + 11 = 24$ .
Source side $\{S, A, B\}$ : crossings $A$ - $C$ ( $8$ ), $A$ - $D$ ( $6$ ), $B$ - $D$ ( $9$ ), $B$ - $E$ ( $4$ ), capacity $8 + 6 + 9 + 4 = 27$ .
Source side $\{S, A, B, C, D\}$ : crossings $B$ - $E$ ( $4$ ), $C$ - $T$ ( $10$ ), $D$ - $T$ ( $7$ ), capacity $4 + 10 + 7 = 21$ .
Source side $\{S, A, B, D\}$ : crossings $A$ - $C$ ( $8$ ), $B$ - $E$ ( $4$ ), $D$ - $T$ ( $7$ ), capacity $8 + 4 + 7 = 19$ .

The smallest found is $19$ . By the maximum-flow minimum-cut theorem the maximum flow is $19$ cars per hour.

(b) State the minimum cut: The cut with source side $\{S, A, B, D\}$ and sink side $\{C, E, T\}$ has capacity $A$ - $C$ ( $8$ ) plus $B$ - $E$ ( $4$ ) plus $D$ - $T$ ( $7$ ) $= 19$ . The bottleneck is a mix of middle and final roads, not one clean layer.
(c) Give an achieving flow: Send $S$ - $A$ $11$ , $S$ - $B$ $8$ , $A$ - $C$ $8$ , $A$ - $D$ $3$ , $B$ - $D$ $4$ , $B$ - $E$ $4$ , $C$ - $T$ $8$ , $D$ - $T$ $7$ , $E$ - $T$ $4$ . Conservation holds: at $A$ , in $11$ , out $8 + 3 = 11$ ; at $D$ , in $3 + 4 = 7$ , out $7$ . The total into $T$ is $8 + 7 + 4 = 19$ .
Check: The flow $19$ equals the minimum cut $19$ and the three cut roads $A$ - $C$ , $B$ - $E$ , $D$ - $T$ are all saturated, confirming the maximum.

What this dot point is asking

The answer

The vocabulary you must use

Flow must be conserved at every vertex

Finding the maximum flow by inspection

Cuts: a cleaner way to pin the maximum

The maximum-flow minimum-cut theorem

Why the two numbers must agree

Multiple sources or multiple sinks

How exam questions ask about network flow

Exam-style practice questions

Practice questions

Related dot points