Contents · 0% complete

Learning objectives
Core idea
Key formulae
Worked examples
Explore the graph
Common mistakes
Exam tip
Guided practice
Practice questions
Challenge
Summary
Quick quiz
Same topic, different board
Past paper questions

Learn7367Paper 3 · Discrete optionNetwork flowsMaximum flow and minimum cut

Network flows · Subtopic 1 of 1

Flows in Networks

Each arc has a capacity; flow is conserved at every vertex except the source $S$ and sink $T$ . A cut separates $S$ from $T$ ; its capacity sums the arcs crossing from the $S$ side to the $T$ side. Maximum flow $=$ minimum cut: find a flow and a cut with equal value and both are optimal.

Edexcel 9FM0 OptionAQA 7367 Paper 3≈ 45 minRevision 2 · updated 2026-10-28

Practise this topicTimed test Ask Salam TutorSwitch board

Section 1 of 14

Learning objectives

Find the capacity of a cut, counting only forward arcs.
Augment flows along paths with spare capacity.
Use max flow–min cut to prove optimality.
Add supersources, supersinks and vertex capacities.

Pause and think

Water flows from a reservoir through pipes to a town. If you draw a line separating them, why can't more water pass than the total capacity of pipes crossing the line?

Section 2 of 14

Core idea

Start herePipes and bottlenecks

Water leaves a reservoir through a web of pipes to a town. However cleverly you route it, every drop has to pass through some set of pipes that separates the two. The narrowest such set is the limit.

The big idea

A cut splits the vertices into a source side and a sink side; its capacity is the total of arcs from the source side to the sink side. Every flow is at most every cut, and the maximum flow equals the minimum cut.

1. Cuts

Network: $SA5$ , $SB4$ , $AB2$ , $AT3$ , $BT6$ .

Worked exampleCut capacities

Find the capacities of $\{S,A\}\mid\{B,T\}$ and $\{S,B\}\mid\{A,T\}$ .

Goal: Two values.
Strategy: Count forward arcs only.

$SB+AB+AT=4+2+3=9$
All leave $\{S,A\}$ .
$SA+BT=5+6=11$
$AB$ goes from the sink side back, so it isn't counted.

Answer

9

and

11

✓ CheckBoth

\ge

any feasible flow ✓.

Why flow

\le

cut

$\text{net flow across any cut}=\text{value of flow}$
Conservation at every inner vertex.
$\text{net}=\text{forward}-\text{backward}\le\text{forward capacities}$
Backward flow only reduces it.

So if a flow equals a cut, both are optimal.

2. Maximum flow

Worked exampleAugmenting paths

Find the maximum flow.

Goal: Value.
Strategy: Add flow along paths with spare capacity.

$SAT:\ 3$
$AT$ saturated.
$SABT:\ 2$
$SA$ now $5$ , $AB$ saturated.
$SBT:\ 4$
$SB$ saturated.

AnswerFlow

9

; the cut

\{S,A\}\mid\{B,T\}

9

, so it's maximal.

✓ CheckAt

B

: in

2+4=6

, out

6

✓.

Labelling procedure

Drawing diagram…

Keep augmenting until a cut matches.

TrickSupersource Several sources? Add a supersource

S

joined to each with capacity equal to its supply.

Edge caseVertex capacities Replace vertex

V

V_1\to V_2

with that capacity.

Pause and think

If $AT$ is widened to $5$ , what's the new maximum flow?

Summary

Cut: forward arcs only.
Flow $\le$ cut.
Max flow = min cut.

Cut: Set of arcs whose removal separates source from sink.
Saturated arc: Arc carrying its full capacity.

HistoryFord and Fulkerson. The max-flow min-cut theorem (1956) came from a US Air Force study of the Soviet rail network: how much could flow, and where was the cheapest place to cut it?

Fun factSports elimination. Max-flow algorithms can decide whether a baseball team is mathematically eliminated from winning its league before the season ends.

Section 3 of 14

Key formulae

Conservation

\text{flow in}=\text{flow out at every vertex except }S,T

Cut capacity

\sum\text{capacities of arcs from }S\text{-side to }T\text{-side}

Theorem

\max\text{ flow}=\min\text{ cut}

TrickBackward arcs. Arcs crossing a cut from the

T

side back to the

S

side contribute

0

to its capacity (or subtract their lower capacity if they have one).

Section 4 of 14

Worked examples

Example 1 · Cut0 / 2 steps

Arcs

SA5

SB4

AB2

AT3

BT6

. Find the cut

\{S,A\}\mid\{B,T\}

Example 2 · Max flow0 / 2 steps

Find the maximum flow.

Section 5 of 14

Explore the graph

The flow network

Loading the interactive graph…

Try this

$S(0,0)$ , $A(2,1.5)$ , $B(2,-1.5)$ , $T(4,0)$ . Capacities $SA5$ , $SB4$ , $AB2$ , $AT3$ , $BT6$ .
Move the line: cuts $\{S\}$ and $\{S,A,B\}$ both have capacity $9$ .

Max flow $9$ .

In the real worldEvacuation planning. Planners model stadium exits and roads as networks to find the maximum number of people who can leave per minute.

Section 6 of 14

Common mistakes

IncorrectAdding backward arcs to a cut

CorrectOnly forward arcs count

Flow back towards

S

doesn't help cross.

IncorrectStopping at a big flow

CorrectShow a cut of equal value

That's the proof of maximality.

IncorrectIgnoring vertex capacities

CorrectSplit the vertex into two joined by an arc

Then it's an ordinary arc capacity.

Me: flow of 9, surely more is possible?

Cut of 9: no.

Section 7 of 14

Exam tip

Exam tipLabel both ways. In the labelling procedure, the forward number is spare capacity and the backward number is the flow you could cancel.

Section 8 of 14

Guided practice

SA-DM-FL-G011 markL1 FoundationNon-calculatorCuts

Arcs

SA5

SB4

AB2

AT3

BT6

. Find the capacity of the cut

\{S\}\mid\{A,B,T\}

Salam Academy Original Practice · Proposed mark scheme

Section 9 of 14

Practice questions

SA-DM-FL-0012 marksL2 StandardNon-calculatorCuts

Find the capacity of the cut

\{S,B\}\mid\{A,T\}

Salam Academy Original Practice · Proposed mark scheme

SA-DM-FL-0022 marksL2 StandardNon-calculatorAugmenting

Find the maximum flow from

S

T

Salam Academy Original Practice · Proposed mark scheme

SA-DM-FL-0031 markL2 StandardNon-calculatorAugmenting

A flow sends

3

along arc

AT

(capacity

3

) and

2

along

AB

(capacity

2

). By conservation, what is the flow in

SA

Salam Academy Original Practice · Proposed mark scheme

More questions on every skill in this subtopic are in the question bank under Practise.

Section 10 of 14

Challenge

SA-DM-FL-0042 marksL3 ExamNon-calculatorExtensions

Vertex

B

can handle at most

5

units. Find the new maximum flow.

Salam Academy Original Practice · Proposed mark scheme

Section 11 of 14

Summary

Conservation at inner vertices.
Cut: forward arcs only.
Max flow = min cut.
Supersources/sinks for several.

Section 12 of 14

Quick quiz

Q1 · SA-DM-FL-Q011 markL1 FoundationNon-calculatorCuts

If you find a flow of value 12 and a cut of capacity 12, then

Salam Academy Original Practice · Proposed mark scheme

Section 13 of 14

Same topic, different board

Specification: 7367 A-level Further Mathematics
Where: Discrete · Network flows
Expected: Capacities, cuts, the maximum flow–minimum cut theorem, flow augmentation, supersources and supersinks.
Calculator: Permitted on all papers.
Typical style: AQA mixes short multiple-choice questions with longer structured ones.
Open in: 7367 · Paper 3

Section 14 of 14

Past paper questions

No past paper questions are tagged to this subtopic yet. We add papers every week.

Browse past papers

Salam Academy original content · Content status: reviewed and published. Syllabus mapping: AQA 7367, First teaching 2017 (official specification).