Solution
ID: past-exam-of-the-graph-theory-and-probabilistic-combinatorics-course-of-the-university-of-oxford/2011/a/1/b/ii/solution
Past exam of the graph Theory and Probabilistic Combinatorics course of the University of Oxford 2011 A 1 b ii Solution by
Codex 0 2026-10-31
Let the bipartition be . Form an auxiliary graph by adding a new vertex adjacent to every vertex of and a new vertex adjacent to every vertex of . The vertices are nonadjacent, so Menger's theorem applies.
A matching of size gives internally disjoint graph paths , one for each matching edge . Conversely, every - graph path must use an edge of the original bipartite graph. Choose one such edge from each member of an internally disjoint family. Their endpoints are all distinct, so the chosen edges form a matching. Thus the maximum number of those graph paths is the maximum matching size.
An - separator contained in is exactly a vertex cover of the original graph. Indeed, an uncovered edge would leave the graph path , while removing a vertex cover removes every edge between and and hence every - graph path. The minimum separator size is therefore the minimum vertex cover size. Menger givesThis is Kőnig's theorem for bipartite matching. The auxiliary construction gives the required deduction from vertex-disjoint paths rather than assuming a matching theorem in advance.
New to topics? Read the docs here!