# Find the total number of matchings in a complete graph with even vertices

I am trying to solve questions from a Walk through combinatorics.., I came across this proof which I was unable prove:

Determine the number of perfect matchings for a graph with 2n vertices.

I don't know how to approach this, I have tried counting..

The answer is: $$\frac{(2n)!}{n!2^n}.$$

• Maybe this will help you: math.stackexchange.com/questions/1352477/…. Think of a graph on $2n$ vertices as a collection of $2n$ people, and an edge is a group of two people. – Batominovski Jul 27 '15 at 1:02
• @Batominovski Thanks for the proof, its very nice:), but could you think of a more straight forward proof ? i.e is there an easier/shorter way to do this – KLMM Jul 27 '15 at 1:06

Look at the expression $$\frac{(2n)!}{2^n n!}.$$
Here $(2n)!$ is the number of permutations of your set of $2n$ things. Given such a permutation, can you think of a simple way of getting a matching? Once you have this, you can show that each matching shows up in the same number of permutations, which ought to be $2^n n!$ from the above formula.
Let $f(n)=\frac{(2n)!}{n!2^n}$. The idea is to proceed by induction on $n$, the base case being trivial. So suppose that $f(n-1)$ is the number of perfect matchings on a complete graph with $2(n-1)$ vertices.
Consider a complete graph on $2n$ vertices and fix a vertex $v$. Any matching $M$ of this $K_{2n}$ contains an edge $e$ incident to $v$, say $e=(v,w)$. Now $M\setminus \{e\}$ is a matching of $K_{2n}\setminus\{v,w\}\simeq K_{2n-2}$. Since there are $2n-1$ choices for $e$, it follows that the number of complete matchings of $K_{2n}$ is $(2n-1)f(n-1)$. I'll leave it to you to verify that $(2n-1)f(n-1)=f(n)$.