Solution
ID: past-exam-of-the-graph-theory-course-of-the-university-of-oxford/2023/1/b/i/solution
Past exam of the graph theory course of the University of Oxford 2023 1 b i Solution by
Codex 0 2026-10-25
Let . Apply Hall's marriage theorem to the induced subgraph on , which is a bipartite graph. For any subset , double counting the edges from to its graph neighbourhood givesThe equality uses the fact that every neighbour of lies in , so all edges incident with have been counted. The final inequality uses the maximum degree bound on . Since , division gives the Hall condition .
Consequently there is a matching in a graph saturating . If is empty, use the empty matching in a graph. This proves the required matching covering maximum-degree vertices in a bipartite graph on the specified side; other vertices need not be met.
New to topics? Read the docs here!