I'm trying to prove that every complete graph has at least one perfect matching, as long as the graph has an even number of vertices. Another proof would be the opposite: If the graph has uneven number of vertices, it is not possible to find a perfect matching.
This sounds trivial, but I couldn't find anything helpful online. I thought maybe the Hall Marriage Theorem would be helpful, but couldn't understand how. I thought maybe of an induction. Any tips?
Best Answer
Hint for the proof with Hall's Marriage Theorem:
Split V(G) in A and B as disjoint sets with |A|=|B|=|V(G)|/2. Erase all edges e={v,w} with v and w being in the same subset A or B. Let G' be the graph resulting from this modification. G' is bipartite. Is there a perfect matching in G'? In case it is, is it the same in G?