Proof that every even complete graph has a perfect matching

Question

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?

Answer 1

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?

Answer 2

Since this graph has obviously Hamilton cycle $$v_1-v_2-\cdots -v_{2n-1}-v_{2n}-v_1$$ just take every pair $v_{2k-1}v_{2k}$ and you are done.