Graph Theory37 sections · 1633 units
Open in Course

König's Theorem

(Matching equals vertex cover)

König's theorem states that in any bipartite graph, the size of the maximum matching equals the size of the minimum vertex cover. A vertex cover is a set of vertices that touches every edge in the graph. This theorem is effective: once you find a max matching of size kk, you immediately know the minimum vertex cover also has size exactly kk.

You can construct the actual vertex cover directly using the matching.