Konig's Theorem

Introduction

Kőnig's theorem connects two different-looking problems in bipartite graphs:

The size of a maximum matching equals the size of a minimum vertex cover.

A matching chooses edges with no shared endpoints. A vertex cover chooses vertices so every edge touches at least one chosen vertex. The theorem gives both the optimal value and a constructive way to recover a minimum cover from a maximum matching.

Problem or motivation

Given a bipartite graph with left vertices $1,\ldots,n$ and right vertices $1,\ldots,m$, find a minimum vertex cover and print which vertices are chosen on both sides.

Trying all subsets of vertices is exponential. We will first find a maximum matching, then transform it into the cover.

Core concept

After finding a maximum matching, start an alternating search from every unmatched left vertex:

• from a left vertex, follow only unmatched edges to the right;
• from a right vertex, follow its matched edge back to the left.

Let $Z_L$ and be the reached vertices on both sides. Then a minimum vertex cover is