König's theorem for bipartite matching

ID: konig-s-theorem-for-bipartite-matching

In a finite bipartite graph, the maximum size of a matching equals the minimum size of a vertex cover. It follows by representing matching as an integral flow and vertex covers as finite-capacity cuts.

New to topics? Read the docs here!