Chapter 16: Directed Graphs and Network Flows

Why does a bottleneck certify the best possible routing?

Network flow theory lies at the intersection of continuous optimization and discrete combinatorics. A routing plan answers a feasibility question: Can the network carry this volume of traffic? A bottleneck answers an impossibility question: Why can no routing plan carry even a fraction more?

When these two perspectives meet, they form one of the most elegant dualities in mathematics: Max-Flow Min-Cut Duality. The maximum flow reachable through a network equals the minimum capacity among all cuts that separate the source from the destination. The same foundational framework unifies bipartite matchings, independent routes, circulation constraints, and graph orientation puzzles.

We build on systems of distinct representatives and matchings and fundamentals of graph theory. All networks in this chapter are finite. A unit may represent a divisible shipment during the proof; when capacities are integers, we establish the existence of a solution that also works for indivisible jobs.

16.1 Directed graphs and DAGs

What & Definitions. A directed graph, or digraph, is a pair $D=(V,A)$ consisting of a set $V$ of vertices and a set $A$ of directed arcs. An arc $e = u\to v$ has tail $u$ and head $v$; orientation defines the direction of traffic. The outdegree $d^+(v)$ counts arcs leaving $v$, and the indegree $d^-(v)$ counts arcs entering it. Each arc contributes once to the sum of outdegrees and once to the sum of indegrees:

$$ \sum_{v\in V}d^+(v)=|A|=\sum_{v\in V}d^-(v). $$

Paths, Cycles, and DAGs. A directed walk follows arc directions. A directed path repeats no vertex. A directed cycle returns to its starting vertex. A directed acyclic graph (DAG) contains no directed cycles. Although a DAG has no directed cycles, its underlying undirected structure can contain cycles. For example, directing the edges of a triangle as $u\to v$, $u\to w$, and $v\to w$ produces a valid DAG.

Topological Ordering. A topological ordering lists every vertex once in a linear sequence such that for every arc $u\to v$, $u$ appears strictly before $v$. A finite digraph is a DAG if and only if it admits at least one topological ordering.

Worked Example: Counting Paths via Topological Order. In a DAG, topological order lets us count all $s$–$v$ directed paths using dynamic programming without listing them individually. Let $P(v)$ be the number of paths from $s$ to $v$. Setting $P(s)=1$, the recurrence for $v \neq s$ is:

$$ P(v)=\sum_{u\to v\in A}P(u). $$

For the motivating network with topological order $s, a, b, t$:

$$ P(s)=1, \quad P(a)=P(s)=1, \quad P(b)=P(s)+P(a)=1+1=2, \quad P(t)=P(a)+P(b)=1+2=3. $$

The three directed paths are $s\to a\to t$, $s\to b\to t$, and $s\to a\to b\to t$. While topological order facilitates path counting, network capacities determine how much flow these paths can carry simultaneously.

Exercise. For arcs $s\to a, s\to b, a\to t, b\to t$, count the topological orderings and $s$–$t$ paths. Then add arc $b\to a$ and repeat. Hint: $s$ must precede both intermediate vertices and $t$ must follow them. Answer: Initially there are 2 topological orderings ($(s,a,b,t)$ and $(s,b,a,t)$) and 2 paths. Adding $b\to a$ forces $b$ before $a$, leaving 1 ordering ($(s,b,a,t)$) and 3 paths ($s\to a\to t$, $s\to b\to t$, $s\to b\to a\to t$).

This chapter emphasizes finite models and proofs. For structural depth, see the Carnegie Mellon graph theory course; for a complete flow implementation, see Princeton's Ford–Fulkerson implementation and API. The latter uses a shortest augmenting path rule. math.cmu.edu

16.2 Max-flow min-cut theorem

Definitions & Flow Network Model. A flow network consists of a finite digraph $D=(V,A)$, distinct source and sink vertices $s,t \in V$, and a non-negative capacity function $c(e) \ge 0$ for each arc $e \in A$. Let $\delta^+(v)$ denote arcs leaving $v$, and $\delta^-(v)$ denote arcs entering $v$. A feasible flow $f: A \to \mathbb{R}_{\ge 0}$ satisfies two core conditions:

1. Capacity Constraint: $0 \le f(e) \le c(e)$ for every arc $e \in A$.
2. Flow Conservation: $\sum_{e\in\delta^+(v)}f(e) = \sum_{e\in\delta^-(v)}f(e)$ for all $v \in V \setminus \{s,t\}$.

The value $|f|$ of a flow is the net throughput leaving the source $s$:

$$ |f|=\sum_{e\in\delta^+(s)}f(e)-\sum_{e\in\delta^-(s)}f(e). $$

By flow conservation, $|f|$ also equals the net flow entering $t$. Incoming arcs at $s$ and outgoing arcs at $t$ are permitted; using net flow keeps the formulation general.

Cuts & Weak Duality. An $s$–$t$ cut is a vertex partition $(S, T)$ with $s \in S$, $t \in T = V \setminus S$. The capacity $C(S)$ of cut $S$ is the sum of capacities of original arcs directed from $S$ into $T$:

$$ C(S)=\sum_{\substack{e=u\to v\in A\\u\in S,\ v\notin S}}c(e). $$

Summing flow conservation over all vertices in $S$ cancels internal arcs within $S$. This yields the Flow–Cut Inequality (Weak Duality):

$$ |f|=f(S,T)-f(T,S)\le C(S). $$

Thus, the value of any feasible flow is bounded above by the capacity of any $s$–$t$ cut. Equality holds if and only if every arc directed from $S$ to $T$ is saturated ($f(e)=c(e)$) and every arc directed from $T$ to $S$ carries zero flow ($f(e)=0$).

Residual Graphs & Augmenting Paths. Given flow $f$, the residual network $D_f$ contains two types of arcs for each original arc $e = u\to v$:

• A forward residual arc $u\to v$ with capacity $c_f(u,v) = c(e) - f(e)$ (available capacity to send more flow).
• A reverse residual arc $v\to u$ with capacity $c_f(v,u) = f(e)$ (ability to push flow back and cancel previous routing).

An augmenting path is a directed path from $s$ to $t$ in $D_f$. Let $\Delta = \min_{e \in P} c_f(e)$ be the path's bottleneck capacity. Pushing $\Delta$ units along $P$ increases $f(e)$ on forward arcs and decreases $f(e)$ on reverse arcs, preserving capacity and conservation constraints while increasing total flow value $|f|$ by $\Delta$.

Max-Flow Min-Cut Theorem. In any finite flow network, the maximum value of a feasible $s$–$t$ flow equals the minimum capacity of an $s$–$t$ cut:

$$ \max_{f\text{ feasible}}|f|= \min_{\substack{S\subseteq V\\s\in S,\ t\notin S}}C(S). $$

Proof Strategy. Let $f^*$ be a maximum flow. Because $f^*$ cannot be augmented further, no directed path from $s$ to $t$ exists in the residual network $D_{f^*}$. Let $S^*$ be the set of all vertices reachable from $s$ in $D_{f^*}$. Since $t \notin S^*$, $(S^*, T^*)$ forms an $s$–$t$ cut.

For any original arc $e = u\to v$ with $u \in S^*, v \in T^*$, we must have $f^*(e) = c(e)$ (otherwise forward arc $u\to v$ would extend reachability into $T^*$). For any arc $e = v\to u$ with $v \in T^*, u \in S^*$, we must have $f^*(e) = 0$ (otherwise reverse arc $u\to v$ would extend reachability into $T^*$). Consequently, $|f^*| = C(S^*)$. By Weak Duality, $f^*$ is a maximum flow and $S^*$ is a minimum cut.

Exercise. If a feasible flow and an $s$–$t$ cut have equal values, must that cut equal the residual reachable set $S^*$? Hint: Minimum cuts need not be unique. Answer: No. In a two-arc unit-capacity chain $s\to v\to t$ with $1$ unit of flow, both $\{s\}$ and $\{s,v\}$ are minimum cuts of capacity $1$. However, only $\{s\}$ is reachable from $s$ in the residual network because arc $s\to v$ is saturated.

16.3 Bipartite matching via network flow

What & Reduction Construction. Let $G=(L\cup R, E)$ be a finite bipartite graph with disjoint left and right vertex sets $L, R$. We construct a directed flow network $D=(V,A)$ as follows:

• Add a source $s$ and a sink $t$. Set $V = \{s\} \cup L \cup R \cup \{t\}$.
• Add directed arcs $s\to u$ with capacity $1$ for all $u \in L$.
• Add directed arcs $v\to t$ with capacity $1$ for all $v \in R$.
• Direct each edge $uv \in E$ as $u\to v$ from $L$ to $R$, with capacity $1$ (or $\infty$).

An integer flow of value $k$ corresponds to a matching of size $k$: each left vertex $u \in L$ receives at most $1$ unit of flow from $s$, and each right vertex $v \in R$ sends at most $1$ unit to $t$. Flow conservation guarantees that middle arcs carrying $1$ unit form a set of vertex-disjoint edges—a valid bipartite matching.

Deriving Hall's Marriage Theorem from Max-Flow Min-Cut. Hall's Condition states that $G=(L\cup R, E)$ has a matching saturating $L$ if and only if for every subset $X \subseteq L$, its neighborhood $N(X) \subseteq R$ satisfies $|N(X)| \ge |X|$.

Proof via Flow Cuts: Assign capacity $\infty$ to all middle arcs $L \to R$, and capacity $1$ to source and sink arcs. Consider a finite cut $S$. Let $X = L \cap S$ and $Y = R \cap S$. To prevent an infinite cut capacity, we must have $N(X) \subseteq Y$, which implies $|Y| \ge |N(X)|$. The capacity of cut $S$ is:

$$ C(S) = (|L| - |X|) + |Y| \ge |L| - |X| + |N(X)|. $$

If $|N(X)| \ge |X|$ for all $X \subseteq L$, then $C(S) \ge |L|$ for every cut $S$. The min-cut capacity is at least $|L|$ (achieved by $S=\{s\}$), so max flow equals $|L|$, yielding a complete matching. Conversely, if $|N(X)| < |X|$ for some $X$, setting $S = \{s\} \cup X \cup N(X)$ creates a cut of capacity $|L| - |X| + |N(X)| < |L|$, certifying that no complete matching exists.

Exercise. Add vertex $c$ to $L$ with a single neighbor $1 \in R$. Can all three left vertices $\{a,b,c\}$ be matched? Hint: Inspect subset $X = \{b,c\}$. Answer: No; $N(X) = \{1\}$, so $|N(X)| = 1 < 2 = |X|$, violating Hall's condition. The maximum matching remains of size 2 (e.g., $\{a2, b1\}$).

16.4 Circulations and lower-bound constraints

Concept & Definitions. A circulation is a flow in a network without explicit source or sink nodes, requiring flow conservation at every vertex $v \in V$. When arcs carry non-zero lower bounds $\ell(e) \le f(e) \le u(e)$, lower bounds represent mandatory throughput commitments (e.g., minimum contract fulfillment).

Auxiliary Transformation. To handle lower bounds, we decompose flow as $f(e) = \ell(e) + x(e)$, where $x(e)$ is the flexible incremental flow bounded by $0 \le x(e) \le u(e) - \ell(e)$. Sending mandatory amount $\ell(e)$ creates an initial flow imbalance $b(v)$ at each vertex $v$:

$$ b(v)=\sum_{e\in\delta^-(v)}\ell(e)-\sum_{e\in\delta^+(v)}\ell(e). $$

Vertex conservation for incremental flow $x$ becomes $\sum_{e\in\delta^+(v)}x(e) - \sum_{e\in\delta^-(v)}x(e) = b(v)$. We construct an auxiliary network $D'$ with new source $\sigma$ and sink $\tau$:

• If $b(v) > 0$ (excess inflow), add arc $\sigma \to v$ with capacity $b(v)$.
• If $b(v) < 0$ (excess outflow), add arc $v \to \tau$ with capacity $-b(v)$.
• Original arcs $e$ receive modified capacity $u(e) - \ell(e)$.

Feasibility Criterion. A feasible circulation respecting bounds $[\ell(e), u(e)]$ exists if and only if the maximum flow in $D'$ saturates all outgoing arcs from $\sigma$ (achieving value $B = \sum_{b(v)>0} b(v)$). Re-adding $\ell(e)$ to the resulting auxiliary flow yields a valid circulation in the original network.

Exercise. On directed cycle $a\to b\to c\to a$, use bounds $([1,3],[2,4],[0,2])$. Find every integral circulation. Hint: All three arc flows must equal a common value $k$ in the intersection of the three intervals. Answer: The intersection $[1,3] \cap [2,4] \cap [0,2] = \{2\}$. Thus $f=(2,2,2)$ is the unique feasible circulation.

16.5 Minimum-cost flow

What & Problem Formulation. Maximum flow maximizes volume regardless of expense. Minimum-cost flow finds the cheapest way to transport a fixed target flow $F$ through a network where each arc $e$ incurs a cost $w(e)$ per unit of throughput:

$$ \min \operatorname{cost}(f) = \sum_{e\in A} w(e) f(e) \quad \text{subject to} \quad |f|=F \quad \text{and} \quad 0 \le f(e) \le c(e). $$

In the residual network $D_f$, forward arcs retain cost $w(e)$, while reverse arcs receive cost $-w(e)$ (reflecting the cost refund obtained when flow is canceled).

Optimality Criterion (Negative Cycle Condition). A feasible flow $f$ of value $F$ is cost-optimal if and only if its residual network $D_f$ contains no directed cycle of negative total cost.

Worked Example: Worker-Job Assignment. Two workers $a,b$ and two jobs $1,2$ require an assignment of flow $F=2$. Source/sink arcs cost $0$. Worker-job costs are: $w(a1)=4, w(a2)=1, w(b1)=2, w(b2)=5$.

Initial assignment $\{a1, b2\}$ costs $4 + 5 = 9$. Its residual cycle $a \to 2 \to b \to 1 \to a$ has cost:

$$ w(a2) - w(b2) + w(b1) - w(a1) = 1 - 5 + 2 - 4 = -6. $$

Canceling this negative cycle pushes 1 unit around the cycle, switching the assignment to $\{a2, b1\}$ and reducing total cost to $9 - 6 = 3$.

Dual Potential Certificate. To certify optimality against fractional flows, assign vertex potentials $h: V \to \mathbb{R}$ such that every residual arc $u\to v$ has a non-negative reduced cost $w_h(u,v) = w(u,v) + h(u) - h(v) \ge 0$. Setting $h(s)=-2, h(a)=0, h(b)=-1, h(1)=1, h(2)=1, h(t)=1$ yields non-negative reduced costs for all residual arcs, proving that cost $3$ is optimal.

Exercise. Change the cost of $a1$ from 4 to 0. Which assignment is cheaper? Hint: Recompute cycle cost $w(a2) - w(b2) + w(b1) - w(a1)$. Answer: Cycle cost becomes $1 - 5 + 2 - 0 = -2$. Initial assignment $\{a1,b2\}$ costs $0 + 5 = 5$, while $\{a2,b1\}$ costs $1 + 2 = 3$. Thus $\{a2,b1\}$ remains cheaper by $2$ units.

16.6 Disjoint paths and connectivity via flows

Arc-Disjoint vs. Internally Vertex-Disjoint Paths.

• Two $s$–$t$ paths are arc-disjoint if they share no common arcs.
• Two $s$–$t$ paths are internally vertex-disjoint if they share no internal vertices (excluding $s$ and $t$).

Setting arc capacities to $1$, an integer flow of value $k$ decomposes into $k$ arc-disjoint $s$–$t$ paths. By Max-Flow Min-Cut, the maximum number of arc-disjoint $s$–$t$ paths equals the minimum number of arcs whose removal disconnects $s$ from $t$ (Directed Arc Form of Menger's Theorem).

Vertex Splitting Transformation. To compute internally vertex-disjoint paths when no direct arc $s\to t$ exists, transform the graph by splitting each intermediate vertex $v \in V \setminus \{s,t\}$ into two nodes $v_{\mathrm{in}}$ and $v_{\mathrm{out}}$:

• Add a directed split arc $v_{\mathrm{in}} \to v_{\mathrm{out}}$ with capacity $1$.
• Redirect incoming arcs to $v_{\mathrm{in}}$, and outgoing arcs from $v_{\mathrm{out}}$ with capacity $\infty$ (or $M=|V|$).

Every path using $v$ must traverse $v_{\mathrm{in}} \to v_{\mathrm{out}}$, enforcing vertex capacity $1$. The minimum cut capacity in the split network equals the minimum size of an $s$–$t$ vertex separator, proving the Directed Vertex Form of Menger's Theorem.

Exercise. Consider arcs $s\to a, a\to v, s\to b, b\to v, v\to c, c\to t, v\to d, d\to t$. Find both disjoint-path maxima. Hint: Inspect intermediate node $v$. Answer: Max arc-disjoint paths = 2 (via $s\to a\to v\to c\to t$ and $s\to b\to v\to d\to t$). Max internally vertex-disjoint paths = 1 (all routes pass through bottleneck vertex $v$).

16.7 Flow and cut integrality

Integrality Theorem. If all arc capacities $c(e)$ in a network are integers, then there exists an optimal maximum flow $f^*$ that is purely integral ($f^*(e) \in \mathbb{Z}_{\ge 0}$ for all $e$). Furthermore, the Ford–Fulkerson algorithm guaranteed to terminate with an integral maximum flow after at most $|f^*|$ augmentations.

Crucial Distinction: Integral Existence vs. Fractional Variants. The Integrality Theorem guarantees the existence of an integer maximum flow; it does not claim that every maximum flow is integral. Fractional maximum flows can be formed by averaging multiple integral flows.

Exercise. In the example above, can a flow of value $2$ exist? Can an integral flow of value $1$ exist? Hint: Check single-arc sink cut $\{c\to t\}$. Answer: Value $2$ is impossible because cut capacity $c(c\to t) = 1$. An integral flow of value $1$ exists along path $s\to a\to c\to t$.

16.8 Flow and orientation problems

What & Problem Statement. Graph orientation assigns a direction to every edge of an undirected graph $G=(V,E)$ such that each vertex $v$ achieves a target outdegree $d_v \in \mathbb{Z}_{\ge 0}$. In tournament scheduling, an edge represents a game, its tail represents the host team, and $d_v$ represents team $v$'s required home-game quota.

Let $m=|E|$ and $E(X)$ be the edges with both endpoints in $X \subseteq V$. Necessary conditions are:

$$ \sum_{v\in V}d_v=m, \quad \text{and} \quad |E(X)|\le\sum_{v\in X}d_v \quad \text{for all } X\subseteq V. $$

Auxiliary DAG Construction. Create a 4-layer flow network:

1. Source $s$ connected to edge nodes $q_e$ with capacity $1$.
2. Edge node $q_{uv}$ connected to vertex nodes $u$ and $v$ with capacity $\infty$. Carrying 1 unit to $u$ assigns $u$ as edge $e$'s tail.
3. Vertex node $v$ connected to sink $t$ with capacity $d_v$.

Max flow value equals $m$ if and only if all sink arcs are saturated, providing a 1-to-1 correspondence with valid orientations.

Worked Example. For $V=\{A,B,C,D\}$ and edges $AB, BC, CD, DA, AC$ ($m=5$), target $(d_A, d_B, d_C, d_D) = (2,1,1,1)$ is realized by orientation $A\to B, B\to C, C\to D, D\to A, A\to C$. By contrast, target $(0,0,3,2)$ violates subset inequality for $X=\{A,B\}$ ($|E(X)| = 1 > 0 = d_A + d_B$), creating an auxiliary cut of capacity $4 < 5$ certifying impossibility.

Exercise. Orient a triangle $K_3$ so every vertex has outdegree $1$. Is an acyclic orientation possible? Hint: Follow outgoing arcs. Answer: The two directed 3-cycles achieve targets $(1,1,1)$, but neither is acyclic. A finite DAG must contain at least one sink ($d^+(v)=0$).

Model a constrained flow and explain its integrality

The same graph can support several questions: prescribe local counts, minimize assignment costs, or enforce an order of precedence. The investigation below combines a flow model for local counts with a DAG test for the orientation it produces. Interpret the graph as a five-game schedule for four teams, with each edge joining the opponents and the tail indicating the home team. The quotas constrain home-game counts; an acyclic orientation adds a separate requirement that all directions follow some ranking of the teams.

An integral solution chooses a single host for each game. A fractional flow might split hosting between the two teams, which is unsuitable for this interpretation. The integrality proof is therefore a modeling requirement, not merely a convenient numerical property. Enumeration of this small instance can check answers, while the cut proof explains why the criterion works for every finite graph of the stated kind.