Unit 8: Graph Coloring, Chromatic Polynomials & Network Flows

1. Proper Vertex Coloring and Chromatic Number

Graph coloring originated from cartographic map coloring in 1852 (Francis Guthrie) and has matured into one of the richest and most computationally challenging branches of discrete mathematics.

Definition 8.1 (Proper Vertex $k$-Coloring): Let $G = (V, E)$ be a simple graph. A proper vertex $k$-coloring is an assignment of colors $c: V \to \{1, 2, \dots, k\}$ such that no two adjacent vertices share the same color:

If such an assignment exists, $G$ is said to be $k$-colorable.

Definition 8.2 (Chromatic Number $\chi(G)$): The chromatic number of $G$, denoted $\chi(G)$, is the minimum integer $k \ge 1$ such that $G$ admits a proper $k$-coloring:

2. Elementary Bounds on $\chi(G)$

Theorem 8.1 (Elementary Coloring Bounds): For any simple graph $G = (V, E)$ with maximum vertex degree $\Delta(G)$ and clique number $\omega(G)$ (the order of the largest complete subgraph $K_r \subseteq G$):

Proof:

1. Lower Bound ($\omega(G) \le \chi(G)$):

Let $K_r \subseteq G$ be a clique of size $r = \omega(G)$. Every pair of vertices in $K_r$ is connected by an edge. Therefore, all $r$ vertices in the clique must receive mutually distinct colors in any proper coloring. Hence $\chi(G) \ge \chi(K_r) = r = \omega(G)$.

2. Upper Bound ($\chi(G) \le \Delta(G) + 1$ via Greedy Coloring):

Let $v_1, v_2, \dots, v_n$ be an arbitrary ordering of $V(G)$. Color the vertices sequentially for $i = 1, 2, \dots, n$: When coloring $v_i$, it has at most $\deg(v_i) \le \Delta(G)$ previously colored neighbors in $\{v_1, \dots, v_{i-1}\}$. These neighbors consume at most $\Delta(G)$ distinct colors from the available set $\{1, 2, \dots, \Delta(G) + 1\}$. By the Pigeonhole Principle, there is at least one color in $\{1, 2, \dots, \Delta(G) + 1\}$ not used by any neighbor of $v_i$. Assign the smallest such available color to $v_i$. This greedy process successfully colors every vertex using at most $\Delta(G) + 1$ colors. Therefore, $\chi(G) \le \Delta(G) + 1$. $\blacksquare$

3. Brooks' Theorem (1941)

The bound $\chi(G) \le \Delta(G) + 1$ is tight for complete graphs $K_n$ ($\Delta = n - 1, \chi = n$) and odd cycle graphs $C_{2k+1}$ ($\Delta = 2, \chi = 3$). Remarkably, R. L. Brooks proved that these are the only connected graphs for which the bound $\chi \le \Delta + 1$ cannot be improved by 1:

Theorem 8.2 (Brooks' Theorem, 1941): Let $G$ be a connected simple graph with maximum degree $\Delta = \Delta(G)$. If $G$ is neither a complete graph ($G \not\cong K_{\Delta+1}$) nor an odd cycle of length $2k+1$ ($\Delta = 2$), then:

Full Formal Proof (Lovász Ordering Technique):

We proceed through the structural cases of connectivity:

1. Case $\Delta \le 2$:

• If $\Delta = 0$, $G \cong K_1$ (complete graph).
• If $\Delta = 1$, $G \cong K_2$ (complete graph).
• If $\Delta = 2$, $G$ is a path $P_n$ or a cycle $C_n$.
• If $G = P_n$, $G$ is bipartite, so $\chi(P_n) = 2 = \Delta$.
• If $G = C_{2k}$, $G$ is an even cycle, which is bipartite, so $\chi(C_{2k}) = 2 = \Delta$.
• If $G = C_{2k+1}$, it is an odd cycle, explicitly excluded.

Thus the theorem holds for all $\Delta \le 2$.

2. Case $\Delta \ge 3$ and $G$ is not 2-connected (has a cut-vertex):

Let $v$ be a cut-vertex of $G$, partitioning $G - v$ into components. Then $G = G_1 \cup G_2$ where $V(G_1) \cap V(G_2) = \{v\}$ and $|V(G_1)|, |V(G_2)| < |V(G)|$. By induction on the number of vertices, $\chi(G_1) \le \Delta(G_1) \le \Delta$ and $\chi(G_2) \le \Delta(G_2) \le \Delta$. Permute colors in $G_2$ so that $v$ receives the same color in both colorings. Gluing $G_1$ and $G_2$ at $v$ yields a proper $\Delta$-coloring of $G$.

3. Case $\Delta \ge 3$ and $G$ is 2-connected but not 3-connected:

If $G$ has a 2-vertex cut $\{u, v\}$, a similar decomposition applies by considering whether $\{u, v\} \in E$ or not.

4. Case $\Delta \ge 3$ and $G$ is 3-connected:

Because $G$ is not complete, there exist three vertices $u, v, w \in V(G)$ such that $\{u, v\} \in E$, $\{v, w\} \in E$, but $\{u, w\} \notin E$ (a 2-path without a chord). Consider $H = G \setminus \{u, w\}$. Since $G$ is 3-connected, $H$ is connected. Construct a spanning tree $T$ of $H$ rooted at $v$. Order the vertices of $H$ in reverse breadth-first/depth-first order starting from the leaves of $T$ towards the root $v$:

• Let $v_n = v$ (the root).
• Let $v_1 = u$ and $v_2 = w$ (the two non-adjacent vertices).
• Let $v_3, v_4, \dots, v_{n-1}$ be the remaining vertices of $H$ in reverse topological order along $T$.

Now execute greedy coloring on this vertex ordering $v_1, v_2, \dots, v_n$:

• Color $v_1 = u$ with color 1.
• Color $v_2 = w$ with color 1 (valid since $\{u, w\} \notin E$!).
• For each $i = 3, 4, \dots, n-1$: vertex $v_i$ has at least one forward neighbor in the tree $T$ that appears after $v_i$ in the ordering.

Therefore, $v_i$ has at most $\deg(v_i) - 1 \le \Delta - 1$ neighbors colored before it. Thus at least one of the $\Delta$ colors $\{1, 2, \dots, \Delta\}$ is free for $v_i$.

• Finally, consider the root $v_n = v$:

$v$ has at most $\Delta$ neighbors in total. Crucially, two of its neighbors are $u$ and $w$, both of which were assigned the same color 1! Therefore, the neighbors of $v$ consume at most $\Delta - 1$ distinct colors! At least one color in $\{1, 2, \dots, \Delta\}$ remains available for $v_n = v$.

Greedy coloring terminates with a proper $\Delta$-coloring of $G$. $\blacksquare$

4. The Five-Color and Four-Color Theorems for Planar Graphs

The famous Four Color Conjecture was posed by Guthrie in 1852, incorrectly proved by Kempe in 1879, refuted by Heawood in 1890 who salvaged the Five Color Theorem, and finally established by Appel and Haken in 1976 using 1,936 reducible computer configurations:

Theorem 8.3 (Heawood's Five-Color Theorem, 1890): Every planar graph $G$ is 5-colorable: $\chi(G) \le 5$.

Full Formal Proof (Kempe Chain Induction):

We proceed by induction on $n = |V(G)|$:

1. Base Case: For $n \le 5$, the result is trivial since $n$ vertices require at most $n \le 5$ colors.

2. Inductive Step: Assume every planar graph with fewer than $n$ vertices is 5-colorable.

Let $G$ be a planar graph with $n$ vertices. By Corollary 7.3, every planar graph has a vertex $v$ with degree $\deg(v) \le 5$. Consider $G - v$, which has $n - 1$ vertices and is planar. By the inductive hypothesis, $G - v$ has a proper 5-coloring $c: V(G - v) \to \{1, 2, 3, 4, 5\}$.

1. If $\deg(v) \le 4$, or if the neighbors of $v$ use at most 4 distinct colors, assign an unused color in $\{1, 2, 3, 4, 5\}$ to $v$.
2. The Critical Case $\deg(v) = 5$:

Suppose the 5 neighbors $v_1, v_2, v_3, v_4, v_5$ of $v$ arranged clockwise around $v$ in a planar embedding receive 5 distinct colors:

Define the Kempe chain $H_{1, 3}$ as the subgraph of $G - v$ induced by all vertices colored with color 1 or color 3.

• Subcase A: $v_1$ and $v_3$ belong to different connected components of $H_{1, 3}$.

In the component containing $v_1$, interchange colors 1 and 3 (swap $1 \leftrightarrow 3$). Since no vertex in this component is adjacent to a vertex of color 1 or 3 outside the component, this remains a valid proper coloring of $G - v$. Now $v_1$ has color 3, and $v_3$ still has color 3. Color 1 is no longer used by any neighbor of $v$! Assign color 1 to $v$.

• Subcase B: $v_1$ and $v_3$ belong to the same connected component of $H_{1, 3}$.

Then there exists an alternating path $P_{1, 3}$ connecting $v_1$ and $v_3$ in $H_{1, 3}$. Together with edges $\{v, v_1\}$ and $\{v, v_3\}$, this forms a Jordan curve $C = P_{1, 3} \cup \{v_1, v\} \cup \{v, v_3\}$ in the plane! Crucially, $v_2$ lies in the interior of $C$, while $v_4$ lies in the exterior of $C$ (or vice versa)!

Now consider the Kempe chain $H_{2, 4}$ induced by colors 2 and 4. Any path in $H_{2, 4}$ connecting $v_2$ and $v_4$ would have to cross the Jordan curve $C$! Since the drawing is planar, vertices of $H_{2, 4}$ cannot cross edges of $C$ without intersecting them. Furthermore, vertices on $C$ have colors in $\{1, 3\}$, which are disjoint from $\{2, 4\}$. Therefore, no path in $H_{2, 4}$ can connect $v_2$ and $v_4$! $v_2$ and $v_4$ MUST belong to different connected components of $H_{2, 4}$!

Interchange colors 2 and 4 in the component containing $v_2$. Now $v_2$ receives color 4, color 2 is vacated around $v$, and we can safely color $v$ with color 2. In all cases, $G$ is properly 5-colored. $\blacksquare$

1. Algebraic Chromatic Polynomials

Introduced by George David Birkhoff in 1912 to tackle the Four Color Problem, the chromatic polynomial translates coloring combinatorics into commutative algebra.

Definition 8.3 (Chromatic Polynomial $P(G, k)$): Let $G = (V, E)$ be a simple graph and $k \in \mathbb{N}$ a positive integer. The chromatic polynomial $P(G, k)$ (also written $\pi_G(k)$) is the function that counts the number of distinct proper vertex colorings of $G$ using at most $k$ colors:

2. Standard Families of Chromatic Polynomials

1. Empty Graph $\bar{K}_n$ ($n$ isolated vertices, $E = \emptyset$):

Each of the $n$ vertices can be colored independently in $k$ ways:

2. Complete Graph $K_n$:

First vertex has $k$ choices, second has $k-1$, and the $i$-th has $k - i + 1$:

(the falling factorial).

3. Tree $T_n$ ($n$ vertices, $n-1$ edges):

Root the tree at $r$. Color $r$ in $k$ ways. Every subsequent vertex in a topological ordering has exactly one colored parent, leaving $k-1$ available choices:

(Notice that all trees on $n$ vertices share identical chromatic polynomials!)

3. The Fundamental Deletion-Contraction Recurrence

The central computational theorem for chromatic polynomials is the Deletion-Contraction Theorem:

Theorem 8.4 (Deletion-Contraction Recurrence): Let $G = (V, E)$ be a simple graph and let $e = \{u, v\} \in E$ be an edge. Let $G - e$ denote the graph obtained by deleting $e$, and $G / e$ denote the graph obtained by contracting edge $e$ (identifying $u$ and $v$ and removing multiple edges). Then for all integers $k$:

Complete Formal Proof:

Let $C(G - e)$ denote the set of all proper $k$-colorings of $G - e$. Partition $C(G - e)$ into two disjoint subsets based on whether the endpoints $u$ and $v$ of $e$ receive different colors or the same color:

1. Case 1 ($c(u) \ne c(v)$):

If $c(u) \ne c(v)$, then the coloring $c$ does not violate the edge condition on $e = \{u, v\}$. Therefore, $c$ is a proper $k$-coloring of the original graph $G = (G - e) + e$. Conversely, every proper coloring of $G$ is a coloring of $G - e$ in which $c(u) \ne c(v)$. Hence:

2. Case 2 ($c(u) = c(v)$):

If $c(u) = c(v)$, we can collapse vertices $u$ and $v$ into a single composite vertex $w = \{u, v\}$ without altering color assignments. The coloring $c$ is a valid proper coloring of the contracted graph $G / e$. Conversely, every proper $k$-coloring of $G / e$ lifts uniquely to a proper coloring of $G - e$ in which $u$ and $v$ have the exact same color. Hence:

Summing the two disjoint subsets:

Rearranging yields:

4. Chromatic Polynomial of Cycles $C_n$

Applying deletion-contraction to a cycle edge $e \in E(C_n)$:

• $C_n - e \cong P_n$ (a path on $n$ vertices, which is a tree, so $P(P_n, k) = k(k-1)^{n-1}$).
• $C_n / e \cong C_{n-1}$ (contracting one edge of an $n$-cycle produces an $(n-1)$-cycle).

Therefore:

By induction from the base case $P(C_3, k) = P(K_3, k) = k(k-1)(k-2) = (k-1)^3 - (k-1)$:

5. Universal Algebraic Properties of $P(G, k)$

Theorem 8.5 (Properties of Chromatic Polynomials): Let $G$ be a graph with $n$ vertices, $m$ edges, and $c$ connected components. Then $P(G, k)$ is a polynomial in $k$ satisfying:

1. $\deg(P(G, k)) = n$.
2. The leading coefficient is $1$ (monic: $P(G, k) = k^n - m k^{n-1} + \dots$).
3. The coefficient of $k^{n-1}$ is exactly $-m = -|E|$.
4. The signs of the coefficients strictly alternate.
5. The smallest power of $k$ with a non-zero coefficient is $k^c$, so $P(G, k)$ has a root of multiplicity $c$ at $k = 0$.
6. $\chi(G)$ is the smallest positive integer $k$ such that $P(G, k) > 0$.

1. Proper Edge Coloring and Chromatic Index

Rather than coloring vertices, we can assign colors to the edges of a network such that concurrently active links never share common terminals.

Definition 8.4 (Edge Coloring & Chromatic Index $\chi'(G)$):

1. A proper edge $k$-coloring of $G = (V, E)$ is a function $c': E \to \{1, 2, \dots, k\}$ such that any two edges sharing a common endpoint receive distinct colors:

1. The chromatic index (or edge chromatic number) $\chi'(G)$ is the minimum number of colors needed for a proper edge coloring:

2. Trivial Degree Bound

At any vertex $v$, all $\deg(v)$ edges incident to $v$ must receive mutually distinct colors. Therefore:

3. König's Line Coloring Theorem for Bipartite Graphs (1916)

For bipartite graphs, this trivial lower bound is always exact:

Theorem 8.6 (König's Theorem on Edge Coloring, 1916): If $G$ is a bipartite graph with maximum degree $\Delta$, then:

Formal Proof (by Induction on Number of Edges):

1. Base Case: For $|E| = 1$, $\Delta = 1$ and $\chi' = 1$.

2. Inductive Step: Suppose every bipartite graph with fewer than $m$ edges has $\chi' = \Delta$.

Let $G$ have $m$ edges and maximum degree $\Delta$. Remove an edge $e = \{u, v\}$. In $G - e$, the maximum degree is $\le \Delta$. By the inductive hypothesis, $G - e$ has a proper edge coloring using $\Delta$ colors $\{1, 2, \dots, \Delta\}$.

In this coloring of $G - e$:

• $\deg_{G-e}(u) \le \Delta - 1$, so there is at least one color $\alpha \in \{1, \dots, \Delta\}$ missing at $u$.
• $\deg_{G-e}(v) \le \Delta - 1$, so there is at least one color $\beta \in \{1, \dots, \Delta\}$ missing at $v$.

• If $\alpha = \beta$: assign color $\alpha$ to edge $e$. This extends to a valid coloring of $G$.
• If $\alpha \ne \beta$: color $\alpha$ is missing at $u$, and color $\beta$ is missing at $v$.

Consider the maximal alternating path $P$ starting at $u$ consisting of edges alternately colored $\beta$ and $\alpha$. Because $G$ is bipartite, $P$ cannot loop back to $u$ (no odd cycles). Furthermore, because $\beta$ is missing at $v$, $P$ cannot end at $v$ with an edge of color $\beta$. Therefore, path $P$ does not reach vertex $v$!

Swap colors $\alpha \leftrightarrow \beta$ along path $P$:

• This preserves valid edge coloring everywhere.
• At vertex $u$, the first edge of $P$ had color $\beta$, which now becomes $\alpha$.
• Color $\beta$ is now missing at $u$ as well as at $v$!
• Assign color $\beta$ to edge $e = \{u, v\}$.

We have obtained a valid $\Delta$-edge coloring of $G$. Thus $\chi'(G) = \Delta$. $\blacksquare$

4. Vizing's Theorem (1964)

For general simple graphs, the chromatic index is constrained within a remarkably narrow window:

Theorem 8.7 (Vizing's Theorem, 1964): For any simple graph $G$ with maximum degree $\Delta$:

Graphs fall into two universal structural classes:

• Class 1 Graphs: $\chi'(G) = \Delta(G)$ (e.g. bipartite graphs, complete graphs $K_{2n}$).
• Class 2 Graphs: $\chi'(G) = \Delta(G) + 1$ (e.g. odd cycles $C_{2k+1}$, complete graphs $K_{2n+1}$, Petersen graph).

Theorem 8.8 (Chromatic Index of Complete Graphs):

1. Flow Networks and Feasibility Conditions

Formulated by Lester R. Ford and Delbert R. Fulkerson in 1956, network flow theory provides the computational foundation for logistics, transportation, telecommunications, and combinatorial optimization.

Definition 8.5 (Flow Network): A flow network is a directed graph $D = (V, E)$ with:

1. A designated source vertex $s \in V$ with indegree 0 (or net supply).
2. A designated sink vertex $t \in V$ with outdegree 0 (or net demand).
3. A non-negative capacity function $c: E \to \mathbb{R}_{\ge 0}$ assigning a maximum throughput $c(u, v)$ to each directed edge $(u, v) \in E$.

Definition 8.6 (Feasible Flow): A flow is a function $f: E \to \mathbb{R}_{\ge 0}$ satisfying:

1. Capacity Constraint:

1. Flow Conservation (Kirchhoff's Current Law):

The total value of the flow, denoted $|f|$, is the net flow leaving the source:

2. Residual Networks and Augmenting Paths

Definition 8.7 (Residual Capacity and Residual Network): Given a flow $f$ in network $D = (V, E)$, the residual network $D_f = (V, E_f)$ defines the available capacity on existing edges and reverse flow cancellation:

• Forward edge residual: $c_f(u, v) = c(u, v) - f(u, v)$ (capacity to push more flow).
• Backward edge residual: $c_f(v, u) = f(u, v)$ (capacity to cancel existing flow).

An edge $(u, v)$ belongs to $E_f$ if and only if $c_f(u, v) > 0$.

An augmenting path is a simple directed path from source $s$ to sink $t$ in the residual network $D_f$. The bottleneck capacity of an augmenting path $P$ is:

Pushing $\gamma(P)$ flow along $P$ increases total flow $|f|$ by exactly $\gamma(P)$.

3. Cuts in Flow Networks and Weak Duality

Definition 8.8 ($s$-$t$ Cut and Cut Capacity): An $s$-$t$ cut is a partition of vertices $V = S \cup T$ such that $s \in S$, $t \in T$, and $S \cap T = \emptyset$. The capacity of the cut, denoted $C(S, T)$, is the sum of capacities of edges directed from $S$ into $T$:

Lemma 8.1 (Weak Duality of Network Flows): For any feasible flow $f$ and any $s$-$t$ cut $(S, T)$:

Proof:

Summing the flow conservation equations over all vertices $u \in S$:

Edges with both endpoints in $S$ cancel in the summation:

4. The Max-Flow Min-Cut Theorem (Ford & Fulkerson, 1956)

Theorem 8.9 (Max-Flow Min-Cut Theorem): In any flow network $D = (V, E)$ with source $s$, sink $t$, and non-negative capacities $c$, the maximum value of an $s$-$t$ flow is equal to the minimum capacity of an $s$-$t$ cut:

Complete Formal Proof:

We prove the equivalence of the following three statements:

1. $f$ is a maximum flow in $D$.
2. The residual network $D_f$ contains no augmenting path from $s$ to $t$.
3. There exists an $s$-$t$ cut $(S, T)$ such that $|f| = C(S, T)$.

• (1 $\implies$ 2): If $D_f$ contained an augmenting path $P$, we could augment $f$ along $P$ by bottleneck $\gamma(P) > 0$, yielding a flow $f'$ with value $|f'| = |f| + \gamma(P) > |f|$, contradicting the maximality of $f$.
• (2 $\implies$ 3): Suppose $D_f$ contains no augmenting path from $s$ to $t$.

Define $S$ as the set of all vertices reachable from $s$ via directed paths in the residual network $D_f$:

Let $T = V \setminus S$. Clearly $s \in S$. Since there is no augmenting path to $t$ in $D_f$, $t \notin S$, so $t \in T$. Thus $(S, T)$ is a valid $s$-$t$ cut.

Now examine any edge $(u, v) \in E$ with $u \in S$ and $v \in T$:

• If $f(u, v) < c(u, v)$, then $c_f(u, v) = c(u, v) - f(u, v) > 0$, meaning $(u, v) \in E_f$.

Then since $u \in S$, $v$ would also be reachable from $s$ in $D_f$, placing $v \in S$, contradiction! Therefore, $f(u, v) = c(u, v)$ for all $u \in S, v \in T$.

Similarly, examine any edge $(v, u) \in E$ with $v \in T$ and $u \in S$:

• If $f(v, u) > 0$, then backward residual $c_f(u, v) = f(v, u) > 0$, meaning $(u, v) \in E_f$.

Again $v$ would be reachable in $D_f$, placing $v \in S$, contradiction! Therefore, $f(v, u) = 0$ for all $v \in T, u \in S$.

Substituting into the net flow equation across $(S, T)$:

• (3 $\implies$ 1): By Weak Duality (Lemma 8.1), $|f'| \le C(S, T)$ for every feasible flow $f'$.

If $|f| = C(S, T)$, no flow can exceed $|f|$, hence $f$ is maximal. $\blacksquare$

1. Matchings in Bipartite Graphs

Definition 8.9 (Matching and Maximum Matching): Let $G = (V, E)$ be an undirected graph.

1. A matching $M \subseteq E$ is a set of pairwise non-adjacent edges (no two edges share a common vertex).
2. A vertex $v$ is saturated (or covered) by $M$ if some edge in $M$ is incident to $v$.
3. A matching $M$ is maximum if $|M| \ge |M'|$ for all matchings $M'$.
4. A matching $M$ is perfect if it saturates every vertex of $G$.

2. Hall's Marriage Theorem (1935)

Philip Hall established the definitive necessary and sufficient condition for the existence of a matching saturating one side of a bipartite graph:

Theorem 8.10 (Hall's Marriage Theorem, 1935): Let $G = (X \cup Y, E)$ be a bipartite graph with bipartition sets $X$ and $Y$. For any subset $S \subseteq X$, let $N(S) = \bigcup_{v \in S} N(v) \subseteq Y$ denote the open neighborhood of $S$. Then $G$ has a matching saturating every vertex in $X$ if and only if Hall's Condition holds:

Complete Formal Proof via Network Flows and Max-Flow Min-Cut:

1. Necessity ($\implies$):

Suppose there exists a matching $M$ saturating all vertices in $X$. Let $S \subseteq X$. Each vertex $u \in S$ is matched by $M$ to a distinct vertex $v_u \in Y$. Because $M \subseteq E$, each $v_u$ is a neighbor of $u$, so $\{v_u : u \in S\} \subseteq N(S)$. Since all $v_u$ are distinct, $|N(S)| \ge |\{v_u : u \in S\}| = |S|$. Hall's condition is strictly necessary.

2. Sufficiency ($\impliedby$):

Assume Hall's Condition $|N(S)| \ge |S|$ holds for all $S \subseteq X$. Construct a flow network $D = (V', E')$ as follows:

• Add a source vertex $s$ and a sink vertex $t$: $V' = \{s, t\} \cup X \cup Y$.
• Add directed edges $(s, x)$ for all $x \in X$, each with capacity $c(s, x) = 1$.
• For every edge $\{x, y\} \in E$ with $x \in X, y \in Y$, add directed edge $(x, y)$ with capacity $c(x, y) = \infty$.
• Add directed edges $(y, t)$ for all $y \in Y$, each with capacity $c(y, t) = 1$.

By the Integrality Theorem for Network Flows, the maximum flow value $|f^*|$ equals the size of the maximum bipartite matching in $G$. A matching saturating $X$ exists if and only if $|f^*| = |X|$.

Suppose for contradiction that $|f^*| < |X|$. By the Max-Flow Min-Cut Theorem (Theorem 8.9), there exists an $s$-$t$ cut $(S', T')$ with capacity:

Let $S_X = S' \cap X$ and $S_Y = S' \cap Y$. Edges crossing the cut from $S'$ to $T'$ consist of:

• Edges from $s$ to $X \cap T'$: there are $|X \setminus S_X| = |X| - |S_X|$ such edges, each of capacity 1.
• Edges from $S_X$ to $Y \cap T'$: if any edge $\{x, y\}$ has $x \in S_X$ and $y \in T'$, its capacity is $\infty$, making $C(S', T') = \infty$, which contradicts $C(S', T') < |X|$.

Therefore, NO edges can go from $S_X$ to $Y \cap T'$, which means $N(S_X) \subseteq S_Y$!

• Edges from $S_Y$ to $t$: there are $|S_Y|$ such edges, each of capacity 1.

Summing the cut capacity:

Since $N(S_X) \subseteq S_Y$, we have $|S_Y| \ge |N(S_X)|$:

By Hall's Condition applied to the subset $S_X \subseteq X$, we have $|N(S_X)| \ge |S_X|$:

This contradicts $C(S', T') < |X|$!

Therefore, the minimum cut capacity must be at least $|X|$. Hence $|f^*| = |X|$, and an integral flow of value $|X|$ exists, providing a matching that saturates every vertex in $X$. $\blacksquare$

3. Operations Research Applications

The Max-Flow Min-Cut and Matching frameworks govern industrial optimization:

1. Birkhoff-von Neumann Theorem: Every doubly stochastic matrix is a convex combination of permutation matrices.

2. Airline Crew & Job Scheduling: Matching flights to crews subject to qualification constraints.

3. Image Segmentation: Min-cut graph cuts partition pixels into foreground and background.

4. Stable Marriage & Gale-Shapley Algorithm: Matching medical residents to hospitals under preference rankings.