Kőnig's theorem

Statement

Let $G$ be a finite bipartite graph. Then the largest number of edges in a matching of $G$ is equal to the smallest number of vertices in a vertex cover of $G$.

Remarks

In every graph, a vertex cover has at least as many vertices as a matching has edges. Kőnig's theorem says that equality holds for bipartite graphs. The theorem fails for other graphs. The triangle $K_3$ has matchings with $1$ edge only, but each vertex cover has $2$ vertices.

History

Dénes Kőnig published the theorem in 1931. Jenő Egerváry found it independently in the same year, in a more general form with weights.

Explanations

L1 human

In a bipartite graph, the most pairs that you can match at once is the same as the fewest vertices that touch every edge. Each of the two numbers gives a certificate that the other one is optimal.