König's Theorem, in depth: three proofs, Δ-colouring bipartite multigraphs, switch scheduling and Dilworth

The statement and why bipartite matters

A matching is a set of edges with no shared endpoint. A vertex cover is a set of vertices touching every edge. In any graph, every matching edge needs its own cover vertex, so ν ≤ τ (maximum matching at most minimum cover). Kőnig's theorem says that in bipartite graphs ν = τ. The triangle shows that bipartiteness is needed: its largest matching has one edge, but two vertices are needed to cover it.

In matrix form, which is how Kőnig and Egerváry stated it: in a 0-1 matrix, the largest number of 1s with no two in the same row or column equals the smallest number of lines (rows or columns) that cover all the 1s. Egerváry's weighted version is the idea behind the Hungarian algorithm for the assignment problem.

Three proofs, three tools

Each proof gives you a different tool, and the tool you need decides which one to remember.

Augmenting paths (constructive). Run a maximum matching algorithm. From every unmatched left vertex, mark everything reachable by alternating paths, Z. The set (left vertices not in Z) together with (right vertices in Z) touches every edge, and it contains exactly one endpoint of each matching edge. That gives a cover of size ν, built in linear time from any maximum matching. Use this when you need the cover itself.

Max-flow min-cut. Add a source joined to every left vertex and a sink joined from every right vertex with unit capacities, and give the original edges infinite capacity. Integral maximum flows are matchings, and finite minimum cuts are vertex covers, so max-flow min-cut gives ν = τ. This is Menger's theorem in disguise. Use it when the problem grows capacities, costs or extra side constraints that a flow solver already handles.

Linear programming. Write matching as maximise Σ x_e with Σ_{e at v} x_e ≤ 1, and vertex cover as its dual. The incidence matrix of a bipartite graph is totally unimodular, so both LPs have integral optimal vertices, and LP duality makes them equal. Use this view to see what happens when the structure breaks. Add an odd cycle and the matching LP gains fractional vertices with value 1/2 on a triangle's edges. Those are what Edmonds' blossom constraints remove. The simplex article covers duality itself.

Hall's theorem as a corollary. A bipartite graph has a matching saturating the left side L exactly when every subset S of L has at least |S| neighbours. Necessity is obvious. For sufficiency, take a minimum cover with left part C_L and right part C_R. The set S = L minus C_L has all its neighbours inside C_R, so Hall's condition gives |C_R| ≥ |S| = |L| - |C_L|, so τ ≥ |L|, and Kőnig gives ν ≥ |L|. Hall's condition is the right thing to report when an assignment is impossible: the set S of jobs with too few qualified workers is the explanation a human can act on.

The edge-colouring theorem

A proper edge colouring needs at least Δ colours, because the edges at a maximum-degree vertex all clash. Kőnig's 1916 theorem says Δ always suffices for bipartite graphs, including multigraphs with parallel edges. General graphs can need Δ + 1, as the triangle shows: Δ = 2, but its three edges pairwise share a vertex and need three colours. (Vizing's theorem says Δ + 1 always suffices for simple graphs.)

The proof is an algorithm. Colour edges one at a time. For edge u-v, u has fewer than Δ coloured edges, so some colour a is free at u. Likewise some colour b is free at v. If a is also free at v, use it. Otherwise follow the path from v that alternates colours a, b, a, b and swap the two colours along it. After the swap a is free at v. The path cannot reach u, because it enters left-side vertices only on a-edges, and u has no a-edge. Then colour u-v with a.

def edge_colouring(edges):
    """edges: (left, right) pairs, parallel edges allowed. Returns (colours, delta)."""
    deg = {}
    for u, v in edges:
        deg[u] = deg.get(u, 0) + 1
        deg[v] = deg.get(v, 0) + 1
    delta = max(deg.values(), default=0)
    at = {x: {} for x in deg}                   # at[x][colour] = (neighbour, edge id)
    free = lambda x: next(k for k in range(delta) if k not in at[x])
    for i, (u, v) in enumerate(edges):
        a, b = free(u), free(v)
        if a in at[v]:                          # a busy at v: flip the a/b path from v
            path, x, k = [], v, a
            while k in at[x]:
                y, j = at[x][k]
                path.append((x, y, j, k))
                x, k = y, (b if k == a else a)
            for x, y, j, k in path:
                del at[x][k], at[y][k]
            for x, y, j, k in path:
                k2 = b if k == a else a
                at[x][k2], at[y][k2] = (y, j), (x, j)
        at[u][a], at[v][a] = (v, i), (u, i)
    colour = [None] * len(edges)
    for x in at:
        for k, (_, j) in at[x].items():
            colour[j] = k
    return colour, delta

Each edge costs at most one path flip of O(V) length, so the run is O(E · V), which is enough for thousands of nodes. For very large multigraphs, Cole, Ost and Schirra gave an O(E log Δ) algorithm. The code was checked on 2,000 random bipartite multigraphs: every colouring was proper and used at most Δ colours.

Worked example: scheduling a switch

A crossbar switch, a network fabric or any set of pairwise exchanges in which each endpoint can handle one transfer per time slot fits the same model. Requests form a matrix D, where D[i][j] is the number of cells input i must send to output j. In each slot, every input sends at most one cell and every output receives at most one, so a slot's transfers form a matching. Build the bipartite multigraph with D[i][j] parallel edges from in_i to out_j. The colour classes of an edge colouring are the slots, and Kőnig says the number of slots equals the busiest port's load, the smallest number possible.

D = [[2, 1, 0],
     [0, 1, 2],
     [1, 1, 1]]
edges = [(f"in{i}", f"out{j}") for i in range(3) for j in range(3) for _ in range(D[i][j])]
colour, slots = edge_colouring(edges)
# slots == 3
# slot 0: in0-out1, in1-out2, in2-out0
# slot 1: in0-out0, in1-out2, in2-out1
# slot 2: in0-out0, in1-out1, in2-out2

When all row and column sums are equal, every slot is a permutation, and the decomposition is the integer form of the Birkhoff-von Neumann theorem: a doubly stochastic matrix is a convex combination of permutation matrices. Switch schedulers use that theorem to turn a long-run rate matrix into a repeating cycle of permutations. The same reasoning bounds any exchange round, such as a shuffle or an all-to-all with uneven per-pair volumes. If each endpoint can drive one transfer at a time, the busiest endpoint's total volume is the lower bound, and an edge colouring achieves it. Real fabrics break the one-transfer assumption with multiple links and contention, so treat this as the baseline a scheduler should be measured against.

From Kőnig to Dilworth

Dilworth's theorem: in a finite partial order, the smallest number of chains (totally ordered subsets) needed to cover every element equals the largest antichain (pairwise incomparable subset). It follows from Kőnig. Split each element x into x_out on the left and x_in on the right, and add an edge x_out-y_in whenever x < y. A matching edge means "y comes right after x in some chain", so a matching of size m links n elements into n - m chains. The vertex cover that Kőnig provides yields an antichain of the same size: the elements with neither copy in the cover.

def kuhn(left, adj):                            # simple augmenting-path matching
    match_r = {}
    def try_(u, seen):
        for v in adj[u]:
            if v not in seen:
                seen.add(v)
                if v not in match_r or try_(match_r[v], seen):
                    match_r[v] = u
                    return True
        return False
    for u in left:
        try_(u, set())
    return match_r                              # right -> left

def dilworth(items, less):                      # less must be transitive
    adj = {x: [y for y in items if less(x, y)] for x in items}
    match_r = kuhn(items, adj)
    nxt = {x: y for y, x in match_r.items()}
    chains = []
    for s in (x for x in items if x not in match_r):
        chain = [s]
        while chain[-1] in nxt:
            chain.append(nxt[chain[-1]])
        chains.append(chain)
    # Koenig: alternating reachability from unmatched left copies
    z_out = {x for x in items if x not in set(match_r.values())}
    z_in, stack = set(), list(z_out)
    while stack:
        x = stack.pop()
        for y in adj[x]:
            if y not in z_in:
                z_in.add(y)
                if y in match_r and match_r[y] not in z_out:
                    z_out.add(match_r[y])
                    stack.append(match_r[y])
    antichain = [x for x in items if x in z_out and x not in z_in]
    return chains, antichain

Worked example. Seven jobs with time windows A(0,2), B(1,3), C(2,5), D(3,4), E(4,6), F(5,7) and G(1,6). A job can follow another on the same worker if it starts after the other ends. The code returns three chains, A-C-F, B-D-E and G, and the antichain {E, F, G}. Those three jobs all run during the interval from 5 to 6, which proves that three workers are necessary as well as sufficient. The checks covered 800 random posets, comparing chain count and antichain size with a brute-force search for the largest antichain.

The same construction gives minimum path covers in DAGs, which answer questions like how many vehicles cover a timetable, how many reusable containers serve a job sequence, or how many pipelines execute a dependency graph. Use the transitive closure when chains may skip elements (Dilworth). Use only direct edges when consecutive elements must be adjacent (vertex-disjoint path cover).

Failure modes

• Applying it to non-bipartite graphs. On a triangle, ν = 1 and τ = 2, and the cover construction outputs something that is not a cover. Check bipartiteness first.
• Assuming bipartite edge colouring on a general conflict graph. The a/b path flip relies on the two sides. On an odd cycle it can loop back to u, and Δ colours may not exist.
• Skipping the transitive closure. Running the Dilworth code on a raw DAG gives a minimum path cover. That can need more chains than Dilworth's answer, and the extracted "antichain" can contain comparable elements.
• Counting ports, not volume. In scheduling, Δ is the largest total demand at any endpoint (a row or column sum), not the number of partners. Using the partner count underestimates the number of slots.
• Ignoring the certificate. Every algorithm here returns a witness: a cover, an antichain, or the busiest port. Assert the witness's size equals the solution's. It is a one-line check that catches most implementation bugs.

Trade-offs

The simple algorithms are usually the right default, because these problems are rarely large enough to need the asymptotically fast ones, and the simple versions are easy to check against their certificates. Reach for Hopcroft-Karp when graphs have hundreds of thousands of edges, and for a general graph colouring heuristic only when the conflict graph genuinely is not bipartite.

What to do next

1. Run the edge-colouring code on the 3×3 demand matrix and confirm three slots, each a permutation.
2. Model one scheduling problem you own (shard rebalancing, interview slots, data shuffles) as a bipartite multigraph, and compare its busiest-endpoint load with your current schedule length.
3. Run the Dilworth code on a real job timetable and check the antichain by hand: those jobs should all overlap.
4. Add certificate assertions (cover size equals matching size, antichain size equals chain count) to any matching code in production.
5. When a resource problem refuses to be bipartite, read about perfect graphs to see how far min-max theorems extend.