Solution

ID: past-exam-of-the-graph-theory-course-of-the-university-of-oxford/2023/1/b/i/solution

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 gives
The 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!