Solution

ID: past-exam-of-the-graph-theory-and-probabilistic-combinatorics-course-of-the-university-of-oxford/2009/a/1/c/iii/solution

False. The complete bipartite graph is -connected. Deleting fewer than vertices leaves at least one vertex in each part and therefore a connected complete bipartite graph; deleting the smaller part disconnects the larger independent set. But its two parts have unequal sizes, so a matching cannot cover them both. Equivalently it has an odd number of vertices. Thus it has no perfect matching.

New to topics? Read the docs here!