Network Flows

Flow networks, the max-flow min-cut theorem, the Ford--Fulkerson method, the Edmonds--Karp algorithm, Dinic's algorithm, and the reduction of bipartite matching to maximum flow.

Folio Official

March 1, 2026

1 Definition of a Flow Network

Definition 1 (Flow network).

A flow network is a tuple

(G, c, s, t)

consisting of a directed graph

G = (V, A)

, a capacity function

c : A \to R_{\geq 0}

, a source

s \in V

, and a sink

t \in V

with

s \neq = t

Definition 2 (Flow).

A flow in a network

(G, c, s, t)

is a function

f : A \to R_{\geq 0}

satisfying:

Capacity constraint: $0 \leq f (u, v) \leq c (u, v)$ for every $(u, v) \in A$ .
Flow conservation: For every vertex $v \neq = s, t$ , $(u, v) \in A \sum f (u, v) = (v, w) \in A \sum f (v, w)$ .

The value of

f

∣ f ∣ = (s, v) \in A \sum f (s, v) - (v, s) \in A \sum f (v, s)

2 Residual Graphs and Augmenting Paths

Definition 3 (Residual graph).

Given a flow

f

, the residual graph

G_{f} = (V, A_{f})

is defined as follows. For each arc

(u, v) \in A

If $f (u, v) < c (u, v)$ , include a forward arc $(u, v) \in A_{f}$ with residual capacity $c_{f} (u, v) = c (u, v) - f (u, v)$ .
If $f (u, v) > 0$ , include a backward arc $(v, u) \in A_{f}$ with residual capacity $c_{f} (v, u) = f (u, v)$ .

Definition 4 (Augmenting path).

An augmenting path is a directed path from

s

t

in the residual graph

G_{f}

. Its bottleneck capacity is

bottleneck (P) = min_{(u, v) \in P} c_{f} (u, v)

3 Cuts and the Max-Flow Min-Cut Theorem

Definition 5 (Cut).

An $s$ - $t$ cut is a partition

(S, T)

V

with

s \in S

and

t \in T

. Its capacity is

c (S, T) = (u, v) \in A u \in S, v \in T \sum c (u, v) .

Theorem 6 (Weak duality).

For any flow

f

and any

s

t

cut

(S, T)

∣ f ∣ \leq c (S, T)

Proof.

Summing the flow conservation equations over all vertices in

S

yields

∣ f ∣ = (u, v) \in A u \in S, v \in T \sum f (u, v) - (v, u) \in A v \in T, u \in S \sum f (v, u) \leq (u, v) \in A u \in S, v \in T \sum c (u, v) = c (S, T) .

□

Theorem 7 (Max-flow min-cut theorem).

The following three statements are equivalent:

$f$ is a maximum flow.
There is no $s$ - $t$ augmenting path in $G_{f}$ .
There exists an $s$ - $t$ cut $(S, T)$ with $∣ f ∣ = c (S, T)$ .

Proof.

(1) \Rightarrow (2)

: If an augmenting path existed, the flow value could be increased, contradicting maximality.

(2) \Rightarrow (3)

: Let

S

be the set of vertices reachable from

s

G_{f}

, and set

T = V ∖ S

. Since there is no augmenting path,

t \in / S

, so

(S, T)

is an

s

t

cut. For every arc

(u, v) \in A

with

u \in S

and

v \in T

, we have

c_{f} (u, v) = 0

, i.e.,

f (u, v) = c (u, v)

. For every arc

(v, u)

with

v \in T

and

u \in S

c_{f} (u, v) = 0

, i.e.,

f (v, u) = 0

. Therefore

∣ f ∣ = u \in S, v \in T \sum f (u, v) - v \in T, u \in S \sum f (v, u) = c (S, T) .

(3) \Rightarrow (1)

: By weak duality, every flow

f^{'}

satisfies

∣ f^{'} ∣ \leq c (S, T) = ∣ f ∣

, so

f

is maximum. □

4 The Ford–Fulkerson Method

The Ford–Fulkerson method starts with the zero flow and repeatedly finds an augmenting path in $G_{f}$ , pushing flow along it.

Algorithm 1: Ford–Fulkerson Method

Input:

Flow network

(G, c, s, t)

Output:

Maximum flow

f

for all

(u, v) \in A

f (u, v) \leftarrow 0

end for

while there exists an augmenting path

P

G_{f}

δ \leftarrow min {c_{f} (u, v) : (u, v) \in P}

// Bottleneck capacity

for all

(u, v) \in P

// Update flow along

P

(u, v) \in A

f (u, v) \leftarrow f (u, v) + δ

// Forward arc

else

f (v, u) \leftarrow f (v, u) - δ

// Backward arc

end if

end for

end while

return

f

Remark 8.

When capacities are rational, the Ford–Fulkerson method terminates in finitely many steps and produces a maximum flow. With irrational capacities, however, non-convergent examples are known. Moreover, a poor choice of augmenting paths can lead to extremely slow convergence even with integer capacities. The Edmonds–Karp algorithm addresses this by always choosing a shortest augmenting path (via BFS).

5 The Edmonds–Karp Algorithm

Theorem 9 (Edmonds–Karp).

When augmenting paths are chosen by BFS (i.e., shortest in terms of number of arcs), the total number of augmentations is

O (∣ V ∣ \cdot ∣ A ∣)

, and the overall running time is

O (∣ V ∣ \cdot ∣ A ∣^{2})

Proof.

The key lemma is that for every vertex

v

, the BFS distance

d_{f} (v)

from

s

G_{f}

is monotonically nondecreasing across augmentations. Under this lemma, each arc that becomes a bottleneck must wait for

d_{f}

to increase by at least

2

before it can be a bottleneck again. Since

d_{f} (v) \leq ∣ V ∣

, each arc is a bottleneck at most

O (∣ V ∣)

times, giving a total of

O (∣ V ∣ \cdot ∣ A ∣)

augmentations. □

6 Dinic's Algorithm

Dinic's algorithm constructs a level graph from $G_{f}$ using BFS, then finds a blocking flow on the level graph. This process is repeated.

Definition 10 (Level graph).

Compute BFS distances

d

from

s

G_{f}

. The level graph

L_{f}

retains only those arcs

(u, v) \in A_{f}

with

d (u) + 1 = d (v)

Theorem 11 (Running time of Dinic's algorithm).

Dinic's algorithm runs in

O (∣ V ∣^{2} \cdot ∣ A ∣)

time.

Proof.

Each phase computes a blocking flow on the level graph in

O (∣ V ∣ \cdot ∣ A ∣)

time. After each phase, the BFS distance from

s

t

strictly increases, so there are at most

∣ V ∣ - 1

phases. □

Remark 12.

On unit-capacity networks (all capacities equal to

1

), Dinic's algorithm runs in

O (∣ A ∣ ∣ V ∣)

time. This is particularly important for bipartite matching (see below).

7 Reduction to Bipartite Matching

Theorem 13 (Bipartite matching via flows).

The maximum matching problem on a bipartite graph

G = (X ⊔ Y, E)

reduces to a maximum flow problem: add a source

s

with arcs of capacity

1

to every vertex in

X

, and add arcs of capacity

1

from every vertex in

Y

to a sink

t

. For each edge

(x, y) \in E

, add an arc

x \to y

of capacity

1

Proof.

By the integrality theorem, the maximum flow in a network with integer capacities can be realized as an integer flow. Each arc has capacity

1

, so the flow on each arc is

0

1

. The capacity constraints on arcs incident to

s

and

t

ensure that each vertex is used by at most one flow-carrying arc. The arcs carrying flow

1

thus form a matching, and the flow value equals the matching size. □

Remark 14.

Applying Dinic's algorithm to this network yields the Hopcroft–Karp algorithm, which runs in

O (∣ E ∣ ∣ V ∣)

time. This reduction also provides an alternative proof of Kö

Graph Theory Discrete Mathematics Textbook Network Flow Max-Flow Min-Cut Ford-Fulkerson

Folio Official

Mathematics "between the lines" — exploring the intuition textbooks leave out, written in LaTeX on Folio.

1 followers·105 articles

Network Flows

1 Definition of a Flow Network

2 Residual Graphs and Augmenting Paths

3 Cuts and the Max-Flow Min-Cut Theorem

4 The Ford–Fulkerson Method

5 The Edmonds–Karp Algorithm

6 Dinic's Algorithm

7 Reduction to Bipartite Matching

Share your expertise with the world

More from Folio Official

Monetizing Your Articles — How to Earn Revenue Safely with Stripe Connect

Mastering Theorem Environments — theorem, definition, proof, and Friends

Combinatorial Designs and Latin Squares: Balanced Arrangements

Burnside's Lemma and P\'olya Enumeration: Counting Under Symmetry