Edge Coloring, König & Max Flow

We study edge coloring (the chromatic index $\chi'(G)$ ), Vizing's theorem, and König's theorem connecting matchings and vertex covers in bipartite graphs. We then introduce network flows — the concept of max flow in a directed network.

Learning Objectives

Define the chromatic index and apply Vizing's theorem

State and apply König's theorem for bipartite graphs

Set up a max flow problem with source, sink, and capacities

Understand the concept of augmenting paths in flow networks

Key Concepts

Edge Coloring & Vizing's Theorem

An edge coloring assigns colors to edges so no two edges sharing a vertex get the same color. The chromatic index $\chi'(G)$ is the minimum number of colors needed.

Vizing's theorem tightly constrains the chromatic index.

-
$\chi'(G) \geq \Delta(G)$ (obvious lower bound: edges at a max-degree vertex need different colors)
-
For loopless graphs: $\Delta(G) \leq \chi'(G) \leq 2\Delta(G) - 1$ (trivial bound)
-
Vizing: $\chi'(G) \leq \Delta(G) + 1$ for simple graphs (at most one extra color)
-
Shannon: $\chi'(G) \leq \lfloor \frac{3}{2}\Delta(G) \rfloor$ for loopless graphs (allows multiple edges)
-
Bipartite graphs are always Class 1: $\chi'(G) = \Delta(G)$ (by König's edge coloring theorem)

König's Theorem

König's theorem is one of the most important results for bipartite graphs: in a bipartite graph, the maximum matching equals the minimum vertex cover.

Combined with Gallai: $\alpha(G) = n - \nu(G)$ for bipartite graphs.

-
Only holds for bipartite graphs (fails for general graphs)
-
Combines with Gallai: for bipartite $G$ , $\alpha(G) = n - \nu(G) = n - \tau(G)$
-
König's edge coloring theorem: $\chi'(G) = \Delta(G)$ for bipartite $G$

Network Flows

A flow network is a directed graph with a source $s$ , sink $t$ , and capacity $c(e)$ on each edge. A flow assigns a value $f(e)$ to each edge satisfying:

-Capacity constraint: $0 \leq f(e) \leq c(e)$
-Conservation: flow in = flow out at every vertex except $s$ and $t$

The value of a flow is the net flow out of $s$ (equivalently, into $t$ ). We want to maximize this.

-
Capacity constraint: flow on each edge ≤ capacity
-
Flow conservation: at every non-source/sink vertex, flow in = flow out
-
Max flow will be computed using Ford-Fulkerson / Edmonds-Karp (next week)

Edmonds-Karp Algorithm

The Edmonds-Karp algorithm is Ford-Fulkerson using BFS to find the shortest augmenting path in the residual graph. This guarantees polynomial running time regardless of capacity values.

The algorithm constructs the auxiliary (residual) graph $H_f$ at each step and uses BFS to find augmenting paths.

-
Uses BFS on the residual graph to find shortest augmenting path
-
Polynomial time: $O(nm^2)$ regardless of capacity magnitudes
-
Basic Ford-Fulkerson without BFS can be exponential with irrational capacities
-
Pseudocode covered in detail in Week 10 (Ford-Fulkerson)

W8: Matchings & Hall's Theorem W10: Max Flow-Min Cut & Ford-Fulkerson