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

A flow network with edge capacities. The source $s$ sends flow through the network to the sink $t$ :

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·107 articles

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

A flow network with edge capacities. The source $s$ sends flow through the network to the sink $t$ :

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.

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·107 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

Paths and Connectivity

Eulerian and Hamiltonian Graphs: Two Classical Traversal Problems

What the max-flow min-cut theorem is really saying — Duality in action

Recurrence Relations and Counting: Solving Linear Recurrences

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

Paths and Connectivity

Eulerian and Hamiltonian Graphs: Two Classical Traversal Problems

What the max-flow min-cut theorem is really saying — Duality in action

Recurrence Relations and Counting: Solving Linear Recurrences