Solution

ID: past-exam-of-the-graph-theory-course-of-the-university-of-oxford/2023/3/d/solution

We verify the Hall condition for . Let . If is empty, then . Suppose . Choose . Its graph neighbourhood is contained in , so the minimum degree hypothesis gives
If , suppose for a contradiction that some vertex exists. All neighbours of lie in , so
contradicting the minimum degree hypothesis. Thus and .
Every subset satisfies the Hall condition. By Hall's marriage theorem, there is a matching in a graph saturating . Since , its edges also cover every vertex of . It is therefore a complete matching, meaning a perfect matching. For , the empty matching in a graph already has this property.

New to topics? Read the docs here!