König's theorem
König's theorem is a fundamental result in graph theory that states that in any bipartite graph, the size of the maximum matching is equal to the size of the minimum vertex cover. A matching is a set of edges without common vertices, while a vertex cover is a set of vertices that includes at least one endpoint of every edge in the graph. This theorem provides a powerful tool for analyzing relationships in bipartite graphs.
The theorem is named after the Hungarian mathematician Dénes Kőnig, who contributed significantly to the field of combinatorics. König's theorem has applications in various areas, including network flow problems and scheduling, making it an essential concept in both theoretical and applied mathematics.