Kőnig's theorem

In every finite bipartite graph, the maximum size of a matching equals the minimum size of a vertex cover. This equality links two optimization problems that appear to measure different things.

Bipartite graph: A graph whose vertices can be divided into two sets so every edge joins vertices in different sets. The theorem applies precisely to graphs with this two-part structure.
Maximum matching: A matching with the greatest possible number of edges in a graph. Its size is the left-hand quantity in the theorem.
Bipartite matching: The problem of finding a largest matching in a bipartite graph. The theorem provides a vertex-cover certificate for the optimum of this central problem.
Konig's line coloring theorem: A theorem that every bipartite multigraph has edge-chromatic number equal to its maximum degree. It is a separate Kőnig theorem about edge coloring, not the matching-cover equality.
Matching (graph theory): A set of graph edges no two of which share a vertex. The theorem's first optimization is to find a matching with as many edges as possible.
Minimum vertex cover: A vertex cover with the fewest possible vertices in a graph. Its size is the right-hand quantity the theorem equates with maximum matching.
Hopcroft–Karp algorithm: An algorithm that finds a maximum-cardinality matching in a bipartite graph in time proportional to (m√n). It efficiently computes the matching side of the equality.
Gallai's theorem: For any finite graph, the maximum matching size plus the minimum edge-cover size equals the number of vertices. It relates matching to a different covering problem and holds beyond bipartite graphs.
Vertex cover: A set of graph vertices containing at least one endpoint of every edge. The theorem's second optimization is to cover every edge with as few vertices as possible.
Independent set (graph theory): A set of vertices no two of which are adjacent. The complement of a vertex cover is an independent set, linking the theorem to another optimization problem.

Linked from 3 pages