Kőnig Bipartite Cover Duality
Turn a maximum bipartite matching into a minimum vertex cover with an alternating-path certificate.
Free theory articleTurn a maximum bipartite matching into a minimum vertex cover with an alternating-path certificate.
Concept & interpretation
In bipartite graphs, Kőnig's theorem establishes a profound duality: the size of the maximum matching is exactly equal to the size of the minimum vertex cover. We can constructively prove this by using alternating paths.
Experiment
Interact with the Kőnig Bipartite Cover Duality module to visualize this process on different graph configurations.
- Open the Kőnig Bipartite Cover Duality module.
- Use the Graph dropdown to select the "Deficient" preset.
- Observe that the maximum matching consists of the edges L0-R0 and L2-R1, and the unmatched vertex L1 initiates the reachability trace.
- Switch to the "Perfect" preset and notice that because every vertex is matched, there are no unreached left vertices, and the cover simply consists of all left vertices.