Konig's theorem

In a bipartite graph, two natural quantities pull in opposite directions. A matching is a set of edges with no shared endpoint — you want as many as possible. A vertex cover is a set of vertices touching every edge — you want as few as possible. Konig's theorem is the striking statement that in any bipartite graph these two optima are equal: the largest matching has exactly the same size as the smallest vertex cover.

Formally, in a bipartite graph the maximum number of edges in a matching equals the minimum number of vertices in a vertex cover. One direction is easy: every edge of a matching needs its own cover vertex, so any cover is at least as large as any matching, giving min-cover >= max-matching. The reverse (equality) is the substance, and the cleanest proof is via flow. Model maximum bipartite matching as max flow with unit capacities; then the max-flow min-cut theorem gives a minimum cut whose capacity equals the matching size, and reading that cut off the bipartition yields a vertex cover of exactly that size. So min vertex cover <= max matching, and the two meet. Konig's theorem is thus the combinatorial face of max-flow min-cut on a matching network.

Konig's theorem matters because it is a min-max duality you can compute and use: finding a maximum matching simultaneously hands you a minimum vertex cover (and, by complementation, a maximum independent set) in bipartite graphs, all in polynomial time. That is special — minimum vertex cover is NP-hard in general graphs, and the bipartite case is one of the few where it is tractable, precisely because of this theorem. It also connects to Hall's theorem: Konig's equality is what makes Hall's condition both necessary and sufficient. The caveat to remember: Konig's theorem holds only for bipartite graphs; in graphs with odd cycles the equality can fail.