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!