Kőnig's theorem

Theorem. In a bipartite graph, the size of a maximum matching equals the size of a minimum vertex cover.

Consequence. Bipartite matching is polynomial (via max-flow or Hopcroft–Karp).

Non-bipartite. The analogous statement fails in general (odd cycles have matching size $1$ but minimum vertex cover size $2$).

Conclusion. Kőnig's theorem is a cornerstone of combinatorial optimization on bipartite graphs.