Problem
COM-B2-M07-P014 Maximal Matching and Edge Covering
#14
★★★★☆ Level 4 of 5
A matching maximal by inclusion is chosen in a graph. Prove that the set of all endpoints of chosen edges intersects every edge of the graph.
If there is an edge with two uncovered endpoints, it can be added.
Suppose there is an edge \(uv\) whose two endpoints are not endpoints of chosen matching edges. Then \(uv\) is disjoint from every edge of the matching, so it can be added. This contradicts maximality by inclusion.
Hence every edge has at least one endpoint among the endpoints of chosen edges.
Leads toward vertex covers and Konig's theorem without formally introducing them.