How to find the number of perfect matchings in complete graphs?

It's just the number of ways of partitioning the six vertices into three sets of two vertices each, right? So that's 15; vertex 1 can go with any of the 5 others, then choose one of the 4 remaining, it can go with any of three others, then there are no more choices to make. $5\times3=15$.

If you just want to get the number of perfect matching then use the formula $\dfrac{(2n)!}{2^n\cdot n!}$ where $2n =$ number of vertices in the complete graph $K_{2n}$.

Detailed Explaination:- You must understand that we have to make $n$ different sets of two vertices each.

First take a vertex. Now we have $(2n-1)$ ways to select another vertex to make the pair.

Now to make another pair we take a vertex and now we have $(2n-3)$ ways to select another vertex. This is because we have already used $2$ vertices in first pair and one vertex is currently in use to make 2nd pair.

Similarly for 3rd pair we will have $(2n-5)$ ways .

When we are making $n^{th}$ pair we will have just one way.

Multiplying all we get $(2n-1)(2n-3)\ldots.3.1$

Now multiply and divide it by even terms as follows $\frac{(2n)(2n-1)(2n-2)(2n-3)\ldots.3.2.1}{(2n)(2n-2)(2n-4)\ldots.4.2}$

Now the numerator will become $(2n)!$ and take $2$ common from each term in denominator. You will get $2^n.(n(n-1)(n-2)\ldots 1)$. Hence the denominator will become $2^n. n!$.

Hence we get the formula as $\frac{(2n)!}{2^n n!}$. Hope this will help.

Gerry is absolutely correct. For 6 vertices in complete graph, we have 15 perfect matching. Similarly if we have 8 vertices then 105 perfect matching exist (7*5*3).

1. For a perfect matching the number of vertices in the complete graph must be even.

2. For a complete graph with n vertices (where n is even), no of perfect matchings is $\frac{n!}{(2!)^{n/2}(n/2)!}$ For $n=2m$, it is $\frac{(2m)!}{(2!)^m m!}$

Using this formula for n=6, the number of partitions = 15

Explanation:

This problem is basically the problem of finding the number of "unordered" partitions of a set.

For partitioning a set of n elements into r unordered partitions of size $n_1, n_2, n_3, ... , n_r$, the formula is $\frac{n!}{n_1!n_2!...n_r!r!}$

For the given question we are to partition a set of size $2m$ into $m$ unordered partitions of size 2 each ie $ \quad n=2m; \quad n_1=n_2=...=n_r=2; \quad r=m$

So the result is: $\frac{(2m)!}{2!2!...(m-times)m!} = \frac{(2m)!}{(2!)^m m!}$

For further on this topic: https://www3.nd.edu/~dgalvin1/10120/10120_S16/Topic07_6p7_Galvin.pdf