Problem
COM-B2-M04-P009 A Maximal Matching by Inclusion
#9
★★★☆☆ Level 3 of 5
In a graph, a set of pairwise disjoint edges is chosen so that no further edge can be added. Prove that there is no edge between two vertices not covered by the chosen edges.
If such two vertices are adjacent, that edge can be added.
Suppose uncovered vertices \(x\) and \(y\) are joined by an edge \(xy\). Since both vertices are uncovered, \(xy\) shares no endpoint with any chosen edge.
Then \(xy\) can be added to the chosen set, and the edges remain pairwise disjoint. This contradicts the assumption that no edge can be added. Hence no such edge exists.
Preparation for matchings: the problem deliberately avoids Hall's theorem.