Solution
ID: past-exam-of-the-short-options-course-of-the-university-of-oxford/2015/7/b/ii/solution
Past exam of the short options course of the University of Oxford 2015 7 b ii Solution by
Codex 0 2026-10-31
Choose a maximum matching and a minimum vertex cover . By Kőnig's theorem for bipartite matching, . Every edge of must have at least one endpoint in , because is a vertex cover. Distinct edges of the matching in a graph have disjoint endpoints, so these requirements already use at least distinct vertices of .
New to topics? Read the docs here!