Kőnig's Theorem: Matchings and Vertex Covers in Bipartite Graphs

The precise statement: a packing equals a covering

Let G = (V, E) be a finite bipartite graph, meaning V splits into two independent sets X and Y so every edge has one endpoint in each. Define:

• A matching M ⊆ E is a set of edges no two of which share a vertex. Its maximum size is the matching number ν(G).
• A vertex cover C ⊆ V is a set of vertices such that every edge has at least one endpoint in C. Its minimum size is the cover number τ(G).

Kőnig's Theorem (1931). If G is bipartite, then ν(G) = τ(G).

One direction is free: any vertex cover must include at least one endpoint of each of the ν disjoint matching edges, and those endpoints are distinct, so τ ≥ ν for every graph. The content of the theorem is the reverse inequality τ ≤ ν, which is exactly what bipartiteness buys you. The two extremal objects are not just equal in size — the proof exhibits a cover of size ν built from a maximum matching.

The picture: alternating paths and a tight bottleneck

Think of a matching as a set of "assignments" — workers X paired with jobs Y. A vertex cover is a set of "guards" you post so that every possible assignment edge is watched by a guard. Kőnig says the cheapest guarding costs exactly as much as the richest assignment.

The mechanism is the alternating path: given a matching M, a path that alternates between non-matching and matching edges. If such a path starts and ends at unmatched vertices, it is augmenting — flipping matched and unmatched edges along it increases the matching by one. A matching is maximum precisely when no augmenting path exists (Berge's lemma). At that stalling point, the vertices reachable by alternating paths from the unmatched X-vertices carve the graph into a tight structure. The "boundary" of this reachable region — the bottleneck the alternating search runs into — is exactly a minimum vertex cover of size ν. The equality is really a statement that the obstruction to a bigger matching is a small cover.

The key idea of the proof: build the cover from the matching

Take a maximum matching M, of size ν. Let U ⊆ X be the M-unmatched vertices in X. Let Z be the set of all vertices reachable from U by alternating paths (non-matching edge from X, matching edge from Y, repeat). Now define the cover

C = (X \ Z) ∪ (Y ∩ Z).

Three facts do all the work. (1) C covers every edge: an edge from X∩Z to Y\Z is impossible, because that Y-vertex would then be reachable and hence in Z. (2) Every vertex of C is matched — no unmatched X-vertex sits in X\Z (they are all in U ⊆ Z), and every Y∩Z vertex is matched (an unmatched reachable Y-vertex would give an augmenting path, contradicting maximality). (3) No matching edge has both endpoints in C. Hence |C| ≤ |M| = ν, giving τ ≤ ν. Combined with the trivial ν ≤ τ, equality follows. The argument is fully constructive — it is the augmenting-path / Hopcroft–Karp algorithm in disguise.

A worked example (and the deficiency version)

Take X = {x₁, x₂, x₃}, Y = {y₁, y₂, y₃} with edges x₁–y₁, x₁–y₂, x₂–y₁, x₂–y₂, x₃–y₃. Here x₁ and x₂ both connect only to {y₁, y₂}. A maximum matching is {x₁–y₁, x₂–y₂, x₃–y₃}? Check: that is a valid matching of size 3 — so ν = 3 and the whole graph is coverable by, say, {y₁, y₂, x₃}, of size 3 = τ. Good.

Now delete edge x₃–y₃, isolating nothing but shrinking reach: edges are just the four among {x₁,x₂}×{y₁,y₂}, plus x₃ has no edges. Then ν = 2 (match x₁–y₁, x₂–y₂). A cover of size 2 is {y₁, y₂}, so τ = 2. Kőnig holds. Hall's connection: Kőnig implies Hall's Marriage Theorem — a perfect matching saturating X exists iff |N(S)| ≥ |S| for all S ⊆ X. The deficiency form gives ν = |X| − maxₛ (|S| − |N(S)|), showing the matching shortfall is governed by the worst Hall-violating set.

Why bipartiteness is essential: the triangle counterexample

Drop bipartiteness and the theorem collapses immediately. In the triangle K₃, any matching uses at most one edge, so ν = 1. But covering all three edges needs at least two vertices — one vertex covers only the two edges at it, leaving the opposite edge uncovered — so τ = 2. Thus ν = 1 < 2 = τ; the gap is exactly the presence of an odd cycle.

This is not an accident: a graph is bipartite if and only if it has no odd cycle (Kőnig, 1936), and odd cycles are precisely the local structures that force τ > ν. The right generalizations restore equality by other means:

• LP duality / total unimodularity: the bipartite incidence matrix is totally unimodular, so the matching LP has an integral optimum matching its dual cover LP — Kőnig is integral LP duality.
• Max-flow min-cut: orient X→Y, add source/sink with unit capacities; a max flow is a max matching and a min cut is a min cover.
• General graphs: replaced by the Tutte–Berge formula and the (harder) Edmonds blossom algorithm.

Why it matters: the wellspring of min–max combinatorics

Kőnig's Theorem is a min–max theorem: it certifies optimality by pairing a solution (a matching) with a proof of its optimality (an equal-size cover). That template — a good characterization giving both a witness and a co-witness — is the beating heart of combinatorial optimization and of the complexity class NP ∩ co-NP.

• Algorithms: Hopcroft–Karp finds a maximum bipartite matching (and hence a minimum cover) in O(E√V) time; the Hungarian algorithm solves weighted assignment via the Kőnig–Egerváry duality.
• Descendants: Menger's theorem (vertex-disjoint paths = min separator), Dilworth's theorem (longest antichain = min chain cover — provable directly from Kőnig), Hall's theorem, and the whole polymatroid / total-dual-integrality edifice.
• Applications: job assignment and scheduling, register allocation, image segmentation (min-cut), rook placements on chessboards with forbidden squares, and Latin-square completion.

In short, Kőnig's 1931 identity is the small, perfect crystal from which linear-programming duality and network flows were later grown.

Four dual parameters and how they relate in general graphs versus bipartite graphs. ν = max matching, τ = min vertex cover, α = max independent set, ρ = min edge cover. Gallai's identities α + τ = n and (for graphs with no isolated vertices) ν + ρ = n hold for ALL graphs; Kőnig's equalities hold only in bipartite graphs.

Relation	General graph	Bipartite graph	Why
ν vs τ	ν ≤ τ (can be strict)	ν = τ (Kőnig)	Weak duality always; equality needs bipartiteness
α vs ρ	α ≤ ρ (can be strict)	α = ρ (Kőnig–Gallai)	Complement of the ν = τ statement via Gallai
ν + ρ	= n (no isolated vertices)	= n	Gallai identity — holds for all graphs
α + τ	= n	= n	Gallai identity — a cover's complement is independent
Example K₃	ν = 1, τ = 2	not bipartite	Odd triangle: one edge matched, need 2 vertices to cover