Lesson 3

Kőnig's Theorem is another beautiful result that connects two seemingly different concepts.

Theorem (Kőnig's Theorem, 1931). In any bipartite graph, the number of edges in a maximum matching is equal to the number of vertices in a minimum vertex cover.

Proof. Let \(\alpha'(G)\) be the size of a maximum matching and \(\tau(G)\) be the size of a minimum vertex cover. We want to prove \(\alpha'(G) = \tau(G)\). We use the same poset as in the proof of Hall's theorem: vertices are the elements, and \(u \prec v\) if \((u,v)\) is an edge. By Dilworth's theorem, the maximum size of an antichain, \(w\), is equal to the minimum number of chains in a chain partition. An antichain in this poset is a set of vertices where no two are connected by an edge. So, \(w = \alpha(G)\), the size of the maximum independent set. A chain partition consists of \(k_{1}\) single-vertex chains and \(k_{2}\) two-vertex chains (edges). The \(k_{2}\) edges form a matching. The total number of vertices is \(|V(G)| = k_{1} + 2k_{2}\), and the number of chains is \(w = k_{1}+k_{2}\). This gives a matching of size \(k_{2} = |V(G)| - w\). Recall the fact that for any graph, a set of vertices is an independent set if and only if its complement is a vertex cover. This means that the size of a maximum independent set and the size of a minimum vertex cover sum up to the total number of vertices: \(\alpha(G) + \tau(G) = |V(G)|\). Putting everything together:

1. From Dilworth's theorem, we can find a chain partition of size \(w = \alpha(G)\) which yields a matching of size \(|V(G)| - w\).
2. From Gallai's identity, the minimum vertex cover has size \(\tau(G) = |V(G)| - \alpha(G) = |V(G)| - w\).