Course contentsShow
← Mathematics
Lesson 2703 of 3,12153. Graph TheoryFree lesson

König's Theorem and Vertex Covers

State and prove König's theorem: in bipartite graphs, the size of a maximum matching equals the minimum vertex cover.

König's Theorem and Vertex Covers

What You'll Learn

You'll discover that in bipartite graphs, the size of a maximum matching equals the size of a minimum vertex cover—a beautiful duality result.

Understanding Vertex Covers

A vertex cover of a graph is a set of vertices such that every edge in the graph has at least one endpoint in the set. Think of it like placing security cameras at intersections: you need enough cameras so that every road segment is watched by at least one camera.

The minimum vertex cover is the smallest such set. Finding this is generally hard, but bipartite graphs have special structure.

König's Theorem

König's Theorem states: In any bipartite graph, the size of a maximum matching equals the size of a minimum vertex cover.

If ν(G) is the maximum matching size and τ(G) is the minimum vertex cover size, then:

ν(G) = τ(G) for bipartite graphs G.

The Proof Sketch

Part 1 (ν ≤ τ): Any vertex cover must include at least one endpoint of each matched edge. Since matched edges are disjoint, we need at least ν vertices in any cover.

Part 2 (τ ≤ ν): This is trickier. Given a maximum matching M, construct a specific vertex cover:

  • Start from unmatched vertices in one partition
  • Use alternating paths (switching between non-matching and matching edges)
  • The vertices touched by this process form a cover of size exactly ν

The construction guarantees every edge is covered and uses exactly as many vertices as the matching size.

Why It Matters

This theorem transforms a difficult optimization problem (minimum vertex cover) into a tractable one (maximum matching) for bipartite graphs. The Hungarian Algorithm you've learned can thus solve both problems simultaneously!

Key Takeaway: König's Theorem establishes that maximum matching size equals minimum vertex cover size in bipartite graphs, revealing a fundamental duality in combinatorial optimization.