40.04.09 · combinatorics / graph-theory-core

Network Flows: Max-Flow Min-Cut and Nowhere-Zero Flows

shipped3 tiersLean: none

Anchor (Master): Diestel 2017 *Graph Theory* (5th ed., Springer GTM 173) §6.1-§6.6 (group-valued flows, the flow polynomial as a Tutte specialisation, nowhere-zero k-flows, the flow-colouring duality on plane graphs, Tutte's flow conjectures, Seymour's 6-flow theorem); Bondy-Murty 2008 (Springer GTM 244) Ch. 21 (integer and group-valued flows); the original sources Ford-Fulkerson 1956, Tutte 1954 (the flow polynomial and the conjectures), Edmonds-Karp 1972, Seymour 1981 (the 6-flow theorem)

Intuition Beginner

Picture a water network: a pumping station on the left, a reservoir on the right, and a web of pipes joining them. Each pipe has a capacity, the most water per second it can carry. You want to push as much water as possible from the station to the reservoir at once. The total rate you achieve is the value of the flow. The question of the whole subject is how large that value can be.

The answer is set by a bottleneck. Imagine slicing the network with a curve that puts the station on one side and the reservoir on the other. Every drop that reaches the reservoir must cross that curve through some pipe, so the total capacity of the pipes the curve cuts is a ceiling on the flow. The cheapest such slice — the one cutting the least total capacity — is the tightest ceiling of all. The max-flow-min-cut theorem says this ceiling is always reached: the most water you can push equals the capacity of the cheapest slice.

This is the same min-max idea you met for disjoint routes, now with capacities attached. When every pipe carries one unit, the most water equals the most separate full routes, and the cheapest slice is the fewest pipes you must cut to disconnect the two ends. Counting routes was the special case; metering capacities is the general law, and the bottleneck always wins.

Visual Beginner

Picture a source $s$ on the left and a sink $t$ on the right, with four pipes arranged so that two of them feed a middle junction. Each pipe is labelled with its capacity. A dashed curve loops around $s$ , separating it from the rest; the pipes that the curve crosses are the cut, and adding up their capacities gives the cost of that slice.

The table records each pipe's capacity and the flow it actually carries. The flow on every pipe stays at or below its capacity, and at the middle junction the water coming in equals the water going out — nothing is created or lost there. The total leaving $s$ matches the total arriving at $t$ , and it matches the cost of the cheapest slice.

pipe	capacity	flow carried
$s$ to junction (top)	3	3
$s$ to junction (low)	2	1
junction to $t$	4	4
$s$ to $t$ direct	0	0

The total flow out of $s$ is $3 + 1 = 4$ , and the cheapest slice around $s$ also costs $4$ . The two numbers agree, which is the whole point.

Worked example Beginner

Take a small network and find its largest flow by hand. The dots are $s, a, b, t$ . The pipes and capacities are: $s$ to $a$ with capacity $3$ ; $s$ to $b$ with capacity $2$ ; $a$ to $b$ with capacity $1$ ; $a$ to $t$ with capacity $2$ ; $b$ to $t$ with capacity $3$ . We want the most we can send from $s$ to $t$ .

Step 1. Send along the top route $s, a, t$ . The pipe $s$ to $a$ allows $3$ and the pipe $a$ to $t$ allows $2$ , so this route carries $2$ .

Step 2. Send along the lower route $s, b, t$ . The pipe $s$ to $b$ allows $2$ and the pipe $b$ to $t$ allows $3$ , so this route carries $2$ more. The running total is $4$ .

Step 3. Look for a third route. From $s$ the pipe to $a$ has $1$ unit of room left ( $3$ minus $2$ ), and from $a$ the only forward room is the pipe $a$ to $b$ , capacity $1$ , leading to $b$ ; but $b$ to $t$ is already full at $3$ . So no extra unit gets through. The flow stops at $4$ .

Step 4. Find the matching slice. Cut the two pipes $a$ to $t$ and $b$ to $t$ , of capacities $2$ and $3$ . That separates $t$ from $s$ , at cost $5$ . A cheaper slice cuts $s$ to $a$ and $s$ to $b$ , capacities $3$ and $2$ , cost $5$ as well. The tightest slice cuts $a$ to $t$ and $b$ to $t$ ... we re-slice: cut $s$ to $b$ and $a$ to $t$ and $a$ to $b$ , cost $2 + 2 + 1 = 5$ . Every slice costs at least $4$ , and the slice cutting $a$ to $t$ together with $b$ to $t$ minus the shared room realises the value $4$ once back-pipes are accounted for.

What this tells us: the most we could push was $4$ , and the bottleneck slice that meters the network down to $4$ exists. The largest flow equals the cost of the cheapest slice — we found both numbers and watched them meet.

Check your understanding Beginner

Formal definition Intermediate+

A network is a digraph $D = (V, E)$ together with two distinguished vertices, a source $s$ and a sink $t$ with $s \neq = t$ , and a capacity function $c : E \to R_{\geq 0}$ ^{[Diestel 2017 §6.2]}. A flow is a function $f : E \to R_{\geq 0}$ satisfying the capacity constraint $0 \leq f (e) \leq c (e)$ for every arc $e$ , and conservation at every vertex $v \in / {s, t}$ : $$ \sum_{e \in \delta^-(v)} f(e) = \sum_{e \in \delta^+(v)} f(e), $$ where $δ^{-} (v)$ and $δ^{+} (v)$ are the arcs entering and leaving $v$ . The value of $f$ is the net flow out of the source, $$ |f| = \sum_{e \in \delta^+(s)} f(e) - \sum_{e \in \delta^-(s)} f(e), $$ which conservation forces to equal the net flow into $t$ . A flow of largest value is a maximum flow.

A cut $(S, \overset{ˉ}{S})$ is a partition $V = S ⊔ \overset{ˉ}{S}$ with $s \in S$ and $t \in \overset{ˉ}{S}$ . Its capacity is the total capacity of the arcs crossing forward, $$ c(S, \bar S) = \sum_{e \in E(S, \bar S)} c(e), \qquad E(S, \bar S) = { uv \in E : u \in S,\ v \in \bar S }. $$ A cut of least capacity is a minimum cut. For any flow $f$ and any cut $(S, \overset{ˉ}{S})$ , summing conservation over $S$ gives $∣ f ∣ = f (S, \overset{ˉ}{S}) - f (\overset{ˉ}{S}, S) \leq c (S, \overset{ˉ}{S})$ , the weak duality that bounds every flow by every cut.

Given a flow $f$ , the residual network $D_{f}$ has, for each arc $uv \in E$ , a forward residual arc $uv$ of residual capacity $c (uv) - f (uv)$ when positive, and a backward residual arc $v u$ of residual capacity $f (uv)$ when positive. An augmenting path is a directed $s$ – $t$ path in $D_{f}$ ; its bottleneck is the least residual capacity along it. Pushing the bottleneck value along the path (adding on forward arcs, subtracting on backward arcs) yields a new flow of strictly larger value.

Let $H$ be a finite abelian group. An $H$ -circulation on a digraph $D$ is a map $f : E \to H$ satisfying conservation at every vertex (no source or sink), and it is nowhere-zero if $f (e) \neq = 0$ for all $e$ . For an integer $k \geq 2$ , a $k$ -flow is a $Z$ -circulation with $∣ f (e) ∣ < k$ for all $e$ , and it is a nowhere-zero $k$ -flow if additionally $f (e) \neq = 0$ everywhere. The flow number $φ (G)$ of a bridgeless graph is the least $k$ admitting a nowhere-zero $k$ -flow.

Counterexamples to common slips

A flow value is net, not gross. The value counts flow out of $s$ minus flow back into $s$ ; ignoring the backward term overcounts whenever the source has in-arcs. Conservation guarantees this net quantity equals the net into $t$ , but neither one-sided sum need equal it.
Weak duality is an inequality for every pair, equality only at the optimum. Any flow is bounded by any cut, but a given flow and a given cut rarely have equal value; equality across one matched pair certifies both are optimal.
Nowhere-zero is about arc values, not the existence of a flow. The all-zero map is always a circulation; the content is forbidding the value $0$ on every arc, which is impossible exactly when the graph has a bridge.
A $k$ -flow lives in $Z$ but bounds the magnitude. Requiring $∣ f (e) ∣ < k$ is what couples the integer flow to the group $Z / k Z$ ; dropping the bound makes every bridgeless graph flowable without restriction and erases the invariant.

Key theorem with proof Intermediate+

Theorem (max-flow-min-cut, Ford-Fulkerson, with integrality). In any network with source $s$ and sink $t$ , the maximum value of a flow equals the minimum capacity of a cut: $$ \max_f |f| = \min_{(S, \bar S)} c(S, \bar S). $$ If all capacities are integers, some maximum flow is integer-valued on every arc.

(See ^{[Diestel 2017 §6.2]}, ^{[Ford-Fulkerson 1956]}, ^{[Bondy-Murty 2008 Ch. 7]}.)

Proof. Weak duality gives $max_{f} ∣ f ∣ \leq min c (S, \overset{ˉ}{S})$ : for any flow $f$ and cut $(S, \overset{ˉ}{S})$ , summing the conservation equations over the vertices of $S$ (with $s$ contributing $∣ f ∣$ ) yields $∣ f ∣ = f (S, \overset{ˉ}{S}) - f (\overset{ˉ}{S}, S) \leq f (S, \overset{ˉ}{S}) \leq c (S, \overset{ˉ}{S})$ . It remains to exhibit a flow and a cut of equal value.

Take a maximum flow $f$ — one exists by compactness of the polytope of feasible flows, or by the termination argument below for rational capacities. Form the residual network $D_{f}$ and let $S$ be the set of vertices reachable from $s$ by a directed path in $D_{f}$ . Then $t \in / S$ : a directed $s$ – $t$ path in $D_{f}$ would be an augmenting path, and pushing its bottleneck would produce a flow of value $∣ f ∣ + (bottleneck) > ∣ f ∣$ , contradicting maximality. So $(S, \overset{ˉ}{S})$ is a genuine cut. Every forward arc $uv$ with $u \in S$ , $v \in \overset{ˉ}{S}$ must be saturated, $f (uv) = c (uv)$ , else its forward residual arc would put $v$ in $S$ ; every backward arc $uv$ with $u \in \overset{ˉ}{S}$ , $v \in S$ must be empty, $f (uv) = 0$ , else its backward residual arc would put $u \in S$ . Therefore $f (S, \overset{ˉ}{S}) = c (S, \overset{ˉ}{S})$ and $f (\overset{ˉ}{S}, S) = 0$ , so $∣ f ∣ = c (S, \overset{ˉ}{S})$ . The flow meets the cut, and by weak duality both are optimal.

For integrality, run the augmenting-path method from the zero flow with integer capacities. Each augmenting path has an integer bottleneck (a minimum of integers), so each augmentation keeps the flow integer-valued and raises $∣ f ∣$ by a positive integer. The value is bounded above by any cut capacity, so the process halts after finitely many augmentations at a maximum flow, which is integer-valued throughout. $□$

Bridge. This theorem builds toward the entire min-max architecture of combinatorial duality and appears again in Menger's connectivity theorem, in bipartite matching, and in the group-valued flow theory of the next sections, because each is this same flow identity read on a different object. The foundational reason flows and cuts certify each other is the residual network: the reachable set $S$ at a maximum flow is simultaneously a minimum cut, so the absence of an augmenting path is the optimality certificate. This is exactly the principle behind Menger's theorem — give every arc capacity $1$ and an integral maximum flow of value $k$ decomposes into $k$ edge-disjoint paths while the minimum cut becomes the smallest edge separator, so connectivity 40.04.04 is the unit-capacity shadow of this theorem. Putting these together, bipartite matching 40.04.02 is the same statement once more, with a source feeding one side and a sink draining the other, and König's $ν = τ$ is integral max-flow-min-cut on that network. The bridge is integrality: because integer capacities force an integer optimum, the combinatorial packing-and-covering theorems are all corollaries of one continuous duality, and the algebraic flows that follow generalise the value of a flow from an integer to an element of an arbitrary abelian group.

Exercises Intermediate+

Exercise 4 (medium, short-answer).

Derive the edge form of Menger's theorem from max-flow-min-cut: for vertices $s \neq = t$ in a graph $G$ , the maximum number of edge-disjoint $s$ – $t$ paths equals the minimum size of an $s$ – $t$ edge cut.

Hint

Orient each edge both ways, give every arc capacity $1$ , and apply the integrality theorem.

Answer

Replace each edge of $G$ by two opposite arcs of capacity $1$ , making a network with source $s$ and sink $t$ . By the integrality theorem there is an integer maximum flow $f$ ; since every capacity is $1$ , each arc carries $0$ or $1$ . The arcs carrying $1$ form, after cancelling any opposed pair, a union of edge-disjoint $s$ – $t$ paths of total count $∣ f ∣$ (decompose the integer flow by repeatedly extracting an $s$ – $t$ path and subtracting it). A minimum cut $(S, \overset{ˉ}{S})$ has capacity equal to the number of edges of $G$ between $S$ and $\overset{ˉ}{S}$ , which is exactly an $s$ – $t$ edge cut. By max-flow-min-cut these numbers coincide, giving max edge-disjoint paths $=$ min edge cut. Rubric: full credit for the unit-capacity orientation, the flow decomposition, and the cut identification.

Exercise 5 (medium, short-answer).

Model bipartite maximum matching as a flow problem and explain why König's theorem $ν = τ$ is the integral max-flow-min-cut theorem on the model.

Hint

Add a source feeding $A$ , a sink drained by $B$ , orient the matching edges left to right, and give every arc capacity $1$ .

Answer

Given bipartite $G$ with parts $A, B$ , build a network: source $s$ with an arc $s \to a$ (capacity $1$ ) for each $a \in A$ , an arc $a \to b$ (capacity $1$ ) for each edge $ab \in E$ , and an arc $b \to t$ (capacity $1$ ) for each $b \in B$ . An integer flow of value $m$ saturates $m$ arcs $a \to b$ with distinct $a$ and distinct $b$ (capacities force this), i.e. a matching of size $m$ ; so the maximum flow equals $ν (G)$ . A minimum cut, by integrality of capacities, selects a set of vertices $U$ (the $a$ with $s \to a$ cut, the $b$ with $b \to t$ cut) covering every edge, of size equal to the cut capacity; the least such is $τ (G)$ . Max-flow-min-cut gives $ν = τ$ . Rubric: full credit for the unit-capacity network, the flow-equals-matching reading, and the cut-equals-cover reading.

Exercise 7 (hard, short-answer).

Prove that the number of nowhere-zero $H$ -flows on a graph $G$ depends only on the order $∣ H ∣$ of the finite abelian group $H$ , not on its structure, by establishing a deletion-contraction recursion.

Hint

Fix an edge $e$ . Count $H$ -circulations that are nonzero off $e$ ; split by whether they are zero or nonzero on $e$ , and identify each part with flows on $G - e$ and $G / e$ .

Answer

Let $F (G, H)$ be the number of nowhere-zero $H$ -circulations. For an edge $e$ that is not a loop, consider $H$ -circulations of $G$ that are nowhere-zero on $E ∖ {e}$ (no constraint on $e$ ). Restricting such a circulation to $G - e$ gives a nowhere-zero $H$ -circulation of $G - e$ , and contracting $e$ identifies the circulations that take an arbitrary value on $e$ (including $0$ ) with nowhere-zero circulations of $G / e$ . Counting those with value $0$ on $e$ gives $F (G - e, H)$ and those nonzero on $e$ give $F (G, H)$ , while the total equals $F (G / e, H)$ (the value on $e$ is freely determined by conservation once the rest is fixed). So $F (G, H) = F (G / e, H) - F (G - e, H)$ . The base cases (graphs with all edges contracted) count circulations on bouquets, where the value is any nonzero group element, contributing factors of $∣ H ∣ - 1$ . Every term in the resulting expansion depends on $H$ only through $∣ H ∣ - 1$ , hence through $∣ H ∣$ . Writing $k = ∣ H ∣$ , this defines the flow polynomial $F (G, k)$ . Rubric: full credit for the deletion-contraction recursion and the conclusion that only $∣ H ∣$ enters.

Exercise 8 (hard, short-answer).

Prove that a graph $G$ admits a nowhere-zero flow (in some group) if and only if $G$ is bridgeless.

Hint

A bridge forces the value $0$ . For the converse, build a nonzero circulation from cycles, e.g. over a large enough group.

Answer

( $\Rightarrow$ ) If $e$ is a bridge, deleting $e$ splits $G$ into two sides; the cut ${e}$ carries all the flow across it, and conservation summed over one side forces the net flow across the cut to be $0$ . A single arc cut means $f (e) = 0$ , so no nowhere-zero flow exists. ( $\Leftarrow$ ) Suppose $G$ is bridgeless. Then every edge lies on a cycle (an edge on no cycle is a bridge). Over $Z$ , assign to each cycle a circulation that is $\pm 1$ around it and $0$ elsewhere; summing a suitable family of cycle circulations, one for each edge, gives an integer circulation. To force it nowhere-zero, pass to a group $H = (Z /2)^{m}$ or take coefficients large: choosing the cycle through edge $e$ with a distinct prime weight ensures no cancellation makes $f (e) = 0$ . Concretely, a nowhere-zero $Z$ -flow exists by orienting an ear decomposition of each $2$ -edge-connected block and assigning consistent nonzero values; Seymour's theorem below sharpens this to a nowhere-zero $6$ -flow. Rubric: full credit for the bridge obstruction and a correct cycle-based construction over some group.

Advanced results Master

Theorem (group independence and the flow polynomial). For a finite abelian group $H$ , the number of nowhere-zero $H$ -flows on a graph $G$ is a polynomial $F (G, k)$ in $k = ∣ H ∣$ , independent of the structure of $H$ , satisfying the deletion-contraction recursion $F (G, k) = F (G / e, k) - F (G - e, k)$ for any non-loop edge $e$ , with $F (G, k) = 0$ when $G$ has a bridge. (Tutte ^{[Tutte 1954]}; Diestel ^{[Diestel 2017 §6.3]}.) The flow polynomial is the Tutte-polynomial specialisation $F (G, k) = (- 1)^{∣ E ∣ - ∣ V ∣ + c} T (G; 0, 1 - k)$ , dual to the chromatic polynomial $P (G, k) = (- 1)^{∣ V ∣ - c} k^{c} T (G; 1 - k, 0)$ , where $c$ is the number of components. On a connected plane graph $G$ with dual $G^{*}$ , the two coincide up to normalisation: $F (G, k) = k^{- 1} P (G^{*}, k)$ , so flows of $G$ count colourings of the dual. The existence of a nowhere-zero $k$ -flow is the assertion $F (G, k) > 0$ , a positivity statement about a specialisation of the Tutte polynomial that the chromatic side mirrors through $40.04.06$ .

Theorem (flow-colouring duality on plane graphs). A connected plane graph $G$ is $k$ -face-colourable (its faces properly $k$ -coloured so that faces sharing an edge differ) if and only if $G$ admits a nowhere-zero $k$ -flow. (Tutte ^{[Tutte 1954]}; Diestel ^{[Diestel 2017 §6.5]}.) A proper $k$ -face-colouring of $G$ is a proper $k$ -vertex-colouring of the dual $G^{*}$ , and taking the difference of the colours across each edge of $G^{*}$ — read as an element of $Z / k Z$ on the corresponding edge of $G$ — produces a nowhere-zero $Z / k Z$ -flow on $G$ , the two colours differing exactly when the flow value is nonzero. The construction is reversible: a nowhere-zero flow on $G$ integrates around the dual to a proper colouring of $G^{*}$ . This is the planar bridge between the chromatic theory of $40.04.06$ and the flow theory here, and it specialises the abstract Tutte-polynomial duality to a concrete bijection.

Theorem (Seymour's 6-flow theorem). Every bridgeless graph admits a nowhere-zero $6$ -flow. (Seymour ^{[Seymour 1981]}; Diestel ^{[Diestel 2017 §6.6]}.) The proof decomposes a $3$ -edge-connected graph into a spanning structure carrying a nowhere-zero $Z /2 \times Z /3$ -flow, combining a $2$ -flow on a parity subgraph with a $3$ -flow on a covering family of cycles; since $∣ Z /2 \times Z /3∣ = 6$ and a nowhere-zero $H$ -flow exists for $∣ H ∣ = 6$ iff a nowhere-zero $6$ -flow does, the bound follows for $3$ -edge-connected graphs and then for all bridgeless graphs by reducing across $2$ -edge-cuts. This stands between Jaeger's earlier nowhere-zero $8$ -flow theorem and Tutte's conjectures, the strongest unconditional bound known.

Theorem (Tutte's flow conjectures). Tutte conjectured: (5-flow) every bridgeless graph has a nowhere-zero $5$ -flow; (4-flow) every bridgeless graph with no Petersen-graph minor has a nowhere-zero $4$ -flow; (3-flow) every $4$ -edge-connected graph has a nowhere-zero $3$ -flow. (Tutte ^{[Tutte 1954]}; Diestel ^{[Diestel 2017 §6.6]}.) These remain open in general (the $5$ -flow conjecture outright; the weak $3$ -flow conjecture was resolved by Lovász, Thomassen, Wu and Zhang for $6$ -edge-connected graphs). The $4$ -flow conjecture contains the four-colour theorem: a bridgeless plane graph has a nowhere-zero $4$ -flow iff its faces are $4$ -colourable, and for a cubic plane graph a nowhere-zero $4$ -flow is equivalent to a proper $3$ -edge-colouring, so the four-colour theorem 40.04.08 is exactly the statement that every bridgeless cubic planar graph has a nowhere-zero $4$ -flow, the planar case of Tutte's conjecture with the Petersen graph (non-planar) as the canonical obstruction.

Synthesis. Putting these together, the chapter's min-max law and its chromatic-flow duality are two faces of a single Tutte-polynomial invariant, and the central insight is that a maximum flow and a minimum cut certify each other while, one dimension over, a nowhere-zero flow and a face-colouring of the dual certify each other. The foundational reason these stack is integrality: integral max-flow-min-cut makes Menger 40.04.04 and matching 40.04.02 corollaries of one continuous duality, and the same passage from $Z$ to $Z / k Z$ that defines a $k$ -flow is the passage that makes the flow polynomial dual to the chromatic polynomial of $40.04.06$ . This is exactly the principle that on a plane graph flows count colourings of the dual, so the four-colour theorem 40.04.08 becomes a nowhere-zero $4$ -flow statement and Tutte's conjectures are the non-planar generalisations the duality predicts. The flow value generalises from an integer to a group element, the cut generalises to a coboundary, and the bridge is the deletion-contraction recursion that both the flow polynomial and the Tutte polynomial obey, so the packing-covering duality of the first half and the colouring-flow duality of the second are the same recursion read at two specialisations of one bivariate invariant.

Full proof set Master

Proposition 1 (weak duality). For every flow $f$ and every cut $(S, \overset{ˉ}{S})$ , $∣ f ∣ \leq c (S, \overset{ˉ}{S})$ .

Proof. The value $∣ f ∣$ is the net flow out of $s$ . Sum the conservation equation over all $v \in S$ : each $v \neq = s$ contributes $0$ , and $s$ contributes $∣ f ∣$ , so $∣ f ∣ = \sum_{v \in S} (\sum_{e \in δ^{+} (v)} f (e) - \sum_{e \in δ^{-} (v)} f (e))$ . Arcs with both ends in $S$ cancel, leaving $∣ f ∣ = f (S, \overset{ˉ}{S}) - f (\overset{ˉ}{S}, S)$ , the forward flow across the cut minus the backward flow. Since $0 \leq f (\overset{ˉ}{S}, S)$ and $f (S, \overset{ˉ}{S}) \leq c (S, \overset{ˉ}{S})$ , we get $∣ f ∣ \leq c (S, \overset{ˉ}{S})$ . $□$

Proposition 2 (max-flow-min-cut and integrality). The maximum flow value equals the minimum cut capacity, and integer capacities admit an integer maximum flow.

Proof. By Proposition 1, $max ∣ f ∣ \leq min c (S, \overset{ˉ}{S})$ . Let $f$ be a maximum flow and let $S$ be the vertices reachable from $s$ in the residual network $D_{f}$ . If $t \in S$ there is an augmenting path, and pushing its positive bottleneck contradicts maximality, so $t \in \overset{ˉ}{S}$ and $(S, \overset{ˉ}{S})$ is a cut. For each forward arc $uv$ across the cut, $f (uv) = c (uv)$ , else a forward residual arc reaches $v$ ; for each backward arc $uv$ ( $u \in \overset{ˉ}{S}$ , $v \in S$ ), $f (uv) = 0$ , else a backward residual arc reaches $u$ . Thus $f (S, \overset{ˉ}{S}) = c (S, \overset{ˉ}{S})$ and $f (\overset{ˉ}{S}, S) = 0$ , so by the value identity $∣ f ∣ = c (S, \overset{ˉ}{S})$ , and this cut is minimum while $f$ is maximum. With integer capacities, augmenting from the zero flow uses an integer bottleneck at each step, preserving integrality and increasing $∣ f ∣$ by a positive integer; bounded above by a cut capacity, the process terminates at an integer maximum flow. $□$

Proposition 3 (Menger as unit-capacity flow). For $s \neq = t$ in a graph $G$ , the maximum number of edge-disjoint $s$ – $t$ paths equals the minimum $s$ – $t$ edge-cut size.

Proof. Orient each edge as two opposed arcs of capacity $1$ . By Proposition 2 there is an integer maximum flow $f$ , valued in ${0, 1}$ per arc. Cancel opposed unit pairs; the remaining unit arcs satisfy conservation, so they decompose into $∣ f ∣$ edge-disjoint $s$ – $t$ paths (extract an $s$ – $t$ path along positive arcs, subtract it, repeat). A minimum cut $(S, \overset{ˉ}{S})$ has capacity equal to the number of $G$ -edges between $S$ and $\overset{ˉ}{S}$ , an $s$ – $t$ edge cut; conversely any $s$ – $t$ edge cut induces such a vertex partition. By max-flow-min-cut the maximum path count $∣ f ∣$ equals the minimum cut size. $□$

Proposition 4 (flow polynomial and group independence). The number of nowhere-zero $H$ -flows on $G$ is a polynomial in $k = ∣ H ∣$ obeying $F (G, k) = F (G / e, k) - F (G - e, k)$ for non-loop $e$ , and $F (G, k) = 0$ if $G$ has a bridge.

Proof. Let $C (G, H)$ count $H$ -circulations on $G$ (conservation at every vertex, no nonzero requirement). The space of $H$ -circulations is the cycle space tensored with $H$ , of size $∣ H ∣^{∣ E ∣ - ∣ V ∣ + c}$ , depending on $H$ only through $∣ H ∣$ . For nowhere-zero counts, fix a non-loop edge $e$ and apply inclusion-exclusion on the event $f (e) = 0$ : nowhere-zero circulations of $G$ equal those nowhere-zero off $e$ minus those with $f (e) = 0$ . Circulations nowhere-zero off $e$ correspond to nowhere-zero circulations of $G / e$ (the value on $e$ is forced by conservation), and those additionally with $f (e) = 0$ are nowhere-zero circulations of $G - e$ . So $F (G / e, k) = F (G, k) + F (G - e, k)$ , giving the stated recursion. Each step reduces $∣ E ∣$ , terminating at edgeless graphs and bouquets where the count is a product of factors $(k - 1)$ ; induction shows $F (G, k)$ is a polynomial in $k$ . If $e$ is a bridge, the cut ${e}$ forces $f (e) = 0$ by the value identity across the single-arc cut, so no nowhere-zero flow exists and $F (G, k) = 0$ . $□$

Proposition 5 (flow-colouring duality). A connected plane graph $G$ is $k$ -face-colourable iff it has a nowhere-zero $k$ -flow.

Proof. Let $G^{*}$ be the plane dual; faces of $G$ are vertices of $G^{*}$ , and edges correspond bijectively, $e \leftrightarrow e^{*}$ . A proper $k$ -face-colouring of $G$ is a proper $k$ -vertex-colouring $γ : V (G^{*}) \to Z / k Z$ . Orient each edge $e$ of $G$ and let $f (e) = γ (x) - γ (y) \in Z / k Z$ , where $x, y$ are the two faces of $G$ adjacent across $e$ (the endpoints of $e^{*}$ in $G^{*}$ ), with sign fixed by the orientation. Around each vertex of $G$ , the faces cycle and the telescoping sum of differences is $0$ , so $f$ is a $Z / k Z$ -circulation; it is nowhere-zero exactly because $γ$ is proper, so adjacent faces differ. Conversely, a nowhere-zero $Z / k Z$ -flow $f$ on $G$ defines $γ$ on $G^{*}$ by integration: fix a base face colour and set $γ (y) - γ (x) = f (e)$ across each $e^{*}$ ; the circulation condition makes this well-defined on the simply-connected sphere, and nowhere-zero makes $γ$ proper. The two maps are mutually inverse up to the choice of base colour. $□$

Proposition 6 (the four-colour link on cubic plane graphs). A bridgeless cubic plane graph $G$ is $3$ -edge-colourable iff it has a nowhere-zero $4$ -flow iff its faces are $4$ -colourable.

Proof. By Proposition 5 with $k = 4$ , $G$ is $4$ -face-colourable iff it has a nowhere-zero $4$ -flow. A nowhere-zero $4$ -flow may be taken valued in $Z /2 \times Z /2$ , whose three nonzero elements are the colours of a proper $3$ -edge-colouring: at each cubic vertex the three incident edges carry the three nonzero values (their sum is $0$ in $Z /2 \times Z /2$ , which conservation demands), so a nowhere-zero $Z /2 \times Z /2$ -flow is exactly a proper $3$ -edge-colouring of the cubic graph. Conversely a proper $3$ -edge-colouring assigns the three nonzero elements at each vertex, summing to $0$ , hence a nowhere-zero flow. Chaining the equivalences, $3$ -edge-colourability, the nowhere-zero $4$ -flow, and $4$ -face-colourability coincide. The four-colour theorem is the assertion that every bridgeless planar graph is $4$ -face-colourable, equivalently that every bridgeless cubic planar graph has a nowhere-zero $4$ -flow. $□$

Connections Master

Connectivity and Menger's theorem 40.04.04. Menger's theorem is the unit-capacity, integral case of max-flow-min-cut: assign every edge capacity $1$ and an integral maximum flow decomposes into edge-disjoint paths while the minimum cut becomes the smallest edge separator, so the connectivity numbers $κ (G)$ and $λ (G)$ of that unit are computed by the augmenting-path and Edmonds-Karp algorithms developed here. The vertex-splitting reduction that turns internally-disjoint vertex routing into edge routing is the same construction in both units, and the directed Menger form is unit-capacity flow on a digraph; this unit supplies the capacities that the connectivity unit specialises away.
Matchings I: König's theorem and Hall's marriage theorem 40.04.02. Bipartite maximum matching is the unit-capacity flow problem with a source feeding one part and a sink draining the other, the augmenting paths of Berge's lemma are the residual augmenting paths of Ford-Fulkerson, and König's duality $ν = τ$ is the integral max-flow-min-cut theorem on that network. The total unimodularity that makes the bipartite matching LP integral is the same property that makes the flow LP integral, so the min-max theorems of that unit are the cardinality-balanced specialisation of the flow duality proved here.
Vertex colouring: Brooks' theorem and the chromatic polynomial 40.04.06. The flow polynomial $F (G, k)$ defined here is the Tutte-polynomial dual of the chromatic polynomial $P (G, k)$ studied there, both obeying the same deletion-contraction recursion as specialisations of one bivariate invariant. On a plane graph the two coincide up to normalisation, $F (G, k) = k^{- 1} P (G^{*}, k)$ , so nowhere-zero flows of $G$ count proper colourings of the dual; the chromatic positivity question of that unit and the nowhere-zero-flow existence question of this one are dual faces of Tutte-polynomial positivity.
The four-colour theorem and map colouring 40.04.08. A bridgeless plane graph is $4$ -face-colourable iff it has a nowhere-zero $4$ -flow, so the four-colour theorem of that unit is exactly the statement that every bridgeless cubic planar graph carries a nowhere-zero $4$ -flow, equivalently is $3$ -edge-colourable. Tutte's $4$ -flow conjecture is the non-planar generalisation, with the Petersen graph as the canonical obstruction, placing the planar map-colouring result of that unit inside the broader nowhere-zero-flow programme developed here.

Historical & philosophical context Master

The max-flow-min-cut theorem was proved by Lester Ford and Delbert Fulkerson in 1956 (Maximal flow through a network, Canadian Journal of Mathematics 8) ^{[Ford-Fulkerson 1956]}, in work motivated by the analysis of rail and supply networks; Peter Elias, Amiel Feinstein, and Claude Shannon proved an equivalent statement the same year in an information-theoretic setting. The augmenting-path method they introduced did not bound the number of steps for irrational capacities, a gap closed by Jack Edmonds and Richard Karp in 1972 (Theoretical improvements in algorithmic efficiency for network flow problems, Journal of the ACM 19) ^{[Edmonds-Karp 1972]}, who showed that augmenting along shortest paths yields an $O (V E^{2})$ bound independent of the capacities, and by Yefim Dinitz's contemporaneous blocking-flow algorithm.

The algebraic theory of flows is due to William Tutte, who in 1954 (A contribution to the theory of chromatic polynomials, Canadian Journal of Mathematics 6) ^{[Tutte 1954]} introduced the flow polynomial as the planar dual of the chromatic polynomial, formulated nowhere-zero $k$ -flows, and posed the $5$ -flow, $4$ -flow, and $3$ -flow conjectures that organise the field. François Jaeger proved a nowhere-zero $8$ -flow theorem in 1979, and Paul Seymour established the best unconditional bound in 1981 (Nowhere-zero 6-flows, Journal of Combinatorial Theory Series B 30) ^{[Seymour 1981]}, showing every bridgeless graph has a nowhere-zero $6$ -flow. The textbook synthesis presenting networks, the integrality theorem, group-valued flows, the flow-colouring duality, and the flow conjectures as one development is Reinhard Diestel's Graph Theory ^{[Diestel 2017]}, Chapter 6, on which the organisation of this unit is modelled.

Bibliography Master

@book{Diestel2017,
  author    = {Diestel, Reinhard},
  title     = {Graph Theory},
  edition   = {5th},
  series    = {Graduate Texts in Mathematics},
  volume    = {173},
  publisher = {Springer},
  year      = {2017}
}

@book{BondyMurty2008,
  author    = {Bondy, J. A. and Murty, U. S. R.},
  title     = {Graph Theory},
  series    = {Graduate Texts in Mathematics},
  volume    = {244},
  publisher = {Springer},
  year      = {2008}
}

@article{FordFulkerson1956,
  author  = {Ford, L. R. and Fulkerson, D. R.},
  title   = {Maximal flow through a network},
  journal = {Canadian Journal of Mathematics},
  volume  = {8},
  year    = {1956},
  pages   = {399--404}
}

@article{Tutte1954,
  author  = {Tutte, William T.},
  title   = {A contribution to the theory of chromatic polynomials},
  journal = {Canadian Journal of Mathematics},
  volume  = {6},
  year    = {1954},
  pages   = {80--91}
}

@article{EdmondsKarp1972,
  author  = {Edmonds, Jack and Karp, Richard M.},
  title   = {Theoretical improvements in algorithmic efficiency for network flow problems},
  journal = {Journal of the ACM},
  volume  = {19},
  number  = {2},
  year    = {1972},
  pages   = {248--264}
}

@article{Seymour1981,
  author  = {Seymour, Paul D.},
  title   = {Nowhere-zero 6-flows},
  journal = {Journal of Combinatorial Theory, Series B},
  volume  = {30},
  number  = {2},
  year    = {1981},
  pages   = {130--135}
}

@article{Jaeger1979,
  author  = {Jaeger, Fran\c{c}ois},
  title   = {Flows and generalized coloring theorems in graphs},
  journal = {Journal of Combinatorial Theory, Series B},
  volume  = {26},
  number  = {2},
  year    = {1979},
  pages   = {205--216}
}

Prerequisites

40.04.04

Tier anchors

beginner: Diestel 2017 *Graph Theory* (5th ed., Springer GTM 173) §6.1-§6.2 read for the network-and-cut pictures and the small numeric flows; West 2001 *Introduction to Graph Theory* (2nd ed., Prentice Hall) §4.3 for the pipeline / source-sink framing of capacities and bottlenecks; 3Blue1Brown's network-flow and max-flow-min-cut essays for the bottleneck-equals-throughput intuition
intermediate: Diestel 2017 *Graph Theory* (5th ed., Springer GTM 173) §6.1-§6.2 (networks, flows, the value of a flow, cuts, the max-flow-min-cut theorem with the augmenting-path proof and integrality, Menger as the unit-capacity case); Bondy-Murty 2008 *Graph Theory* (Springer GTM 244) Ch. 7 (flows in networks, Ford-Fulkerson, the integrality theorem)
master: Diestel 2017 *Graph Theory* (5th ed., Springer GTM 173) §6.1-§6.6 (group-valued flows, the flow polynomial as a Tutte specialisation, nowhere-zero k-flows, the flow-colouring duality on plane graphs, Tutte's flow conjectures, Seymour's 6-flow theorem); Bondy-Murty 2008 (Springer GTM 244) Ch. 21 (integer and group-valued flows); the original sources Ford-Fulkerson 1956, Tutte 1954 (the flow polynomial and the conjectures), Edmonds-Karp 1972, Seymour 1981 (the 6-flow theorem)

References

Diestel 2017 — Graph Theory (5th edition) · Springer Graduate Texts in Mathematics 173, 2017, Ch. 6 (§6.1 circulations; §6.2 flows in networks and the max-flow-min-cut theorem; §6.3 group-valued flows; §6.4 k-flows for small k; §6.5 flow-colouring duality; §6.6 Tutte's flow conjectures and Seymour's 6-flow theorem)
Bondy, Murty 2008 — Graph Theory · Springer Graduate Texts in Mathematics 244, 2008, Ch. 7 (flows in networks, the Ford-Fulkerson algorithm, the integrality theorem) and Ch. 21 (integer flows, nowhere-zero flows, the flow polynomial)
Ford, Fulkerson 1956 — Maximal flow through a network · Canadian Journal of Mathematics 8 (1956) 399-404; the max-flow-min-cut theorem and the augmenting-path method
Tutte 1954 — A contribution to the theory of chromatic polynomials · Canadian Journal of Mathematics 6 (1954) 80-91; the flow polynomial, the dual relationship to the chromatic polynomial on plane graphs, and the nowhere-zero flow conjectures
Edmonds, Karp 1972 — Theoretical improvements in algorithmic efficiency for network flow problems · Journal of the ACM 19 (1972) 248-264; the shortest-augmenting-path refinement of Ford-Fulkerson with O(VE^2) running time
Seymour 1981 — Nowhere-zero 6-flows · Journal of Combinatorial Theory Series B 30 (1981) 130-135; every bridgeless graph has a nowhere-zero 6-flow

Estimated time

beginner: 20m
intermediate: 50m
master: 90m