perfect match graph theory

Question

The question:

Prove that if $G$ is a graph with $2n$ vertices and degree of each one is at least $n$, then there is perfect match in G.

hint???

Answer 1

Prove each step in sequence or use previous results from your book/lecture notes

Step 1:

• A graph with $2n$ vertices where every degree is at least $n$ must be connected

Step 2:

• A graph with $2n$ vertices where every degree is at least $n$ must have a Hamiltonian cycle.

Step 3: (hidden with spoiler tag)

- A graph with a Hamiltonian cycle and an even number of vertices must have a perfect matching.