Problem
COM-B2-M08-P005 Maximal by Inclusion
#5
★★☆☆☆ Level 2 of 5
In a graph, a matching is chosen so that no edge can be added to it. Prove that there is no edge between two uncovered vertices.
Such an edge could be added.
If two uncovered vertices are adjacent, that edge has no common endpoint with any chosen edge. It can be added to the matching, a contradiction.
Repeats the extremal idea in matching context.