19
$\begingroup$

In wikipedia FKT algorithm is given for planar graphs. Not anything for complete graphs. I need to find the number of perfect matchings in complete graph of six vertices.

$\endgroup$
2
  • 3
    $\begingroup$ Here is an alternate way to do this via recursion. Let $a_n$ denote the number of perfect matchings in $K_{2n}$. Then clearly, $a_1 = 1$. Now in $K_{2n}$ (where $n \geq 2$), pick any vertex $u$, you can match it with $(2n-1)$ vertices. After matching $u$, you are left with $2n-2$ vertices. Thus, $a_n = (2n-1)a_{n-1}$. So, $a_n = (2n-1)(2n-3)\dots(1)$. $\endgroup$
    – feynhat
    May 7, 2018 at 7:27
  • $\begingroup$ This is also called double factorial: $a_n=(2n-1)!!$ $\endgroup$
    – RobPratt
    Feb 13, 2020 at 22:02

7 Answers 7

17
$\begingroup$

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$.

$\endgroup$
8
  • 18
    $\begingroup$ Side note. For a general complete graph on $2n$ vertices, this number comes out to be $\frac{(2n)!}{n! 2^{n}}$. $\endgroup$
    – Srivatsan
    Aug 31, 2011 at 11:19
  • 3
    $\begingroup$ In other words, it's the product of the odd numbers up to the number of vertices. $\endgroup$
    – becko
    Sep 1, 2012 at 20:13
  • $\begingroup$ Or even for $\#V = 2n$ we have $(2n - 1)!!$ perfect matchings. $\endgroup$
    – Mmmh mmh
    May 17, 2014 at 10:22
  • 1
    $\begingroup$ @Srivatsan in one of the books I have, the solution is same, but it explains it as: "The number of perfect matchings in a complete graph of n vertices, where n is even, reduces to the problem of finding unordered partitions of vertex set of the type p(2n;2,2,2,...n times) = $\frac{(2n)!}{(2!)^nn!}$ ", Is p(2n;2,2,2,...n times) some series? Book does not elaborate much. Also notice $(2!)^n$ in the denominator, not just $2^n$ thought both are same. Just guessing if this is some series unknown to me, then 2! must be having some significance in series expansion $\endgroup$
    – Maha
    Dec 11, 2014 at 19:15
  • 2
    $\begingroup$ @awell, I think $p(m;a_1,\dots,a_r)$ just means number of partitions of a set of size $m$ into $r$ subsets, one of size $a_1$, ..., one of size $a_r$. The formula for that is $m!/((a_1!)\cdots(a_r)!)$. It comes from repeated application of the formula for the number of combinations of $m$ things taken $a$ at a time, $m!/(a!(m-a)!)$. $\endgroup$ Dec 11, 2014 at 22:00
3
$\begingroup$

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.

$\endgroup$
1
$\begingroup$

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).

$\endgroup$
1
$\begingroup$
  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

$\endgroup$
2
  • $\begingroup$ Use LaTeX please. $\endgroup$ Jun 14, 2019 at 14:36
  • $\begingroup$ @MichaelRozenberg Done in LaTex now. $\endgroup$ Jun 14, 2019 at 14:44
0
$\begingroup$

This problem is equivalent to finding set of $n$ disjoint pairs. Lets say there are $2n$ vertices then $\frac{2n}{2^n}$ is the number of ways you can have these $n$ pairs. i.e, ways to make disjoint pairs out of these. E.g, If you had vertices $1,2,3,4$ then one of the possible way to make set out of this would be $\{(1,2),(3,4)\}$. Finally, as set is an unordered collection so final solution becomes $\frac{2n}{2^n*n!}$.

$\endgroup$
0
$\begingroup$

Another way of arriving at the formula $(2n-1)!! \left( = \frac{(2n)!}{2^n (n!)} \right)$ for $2n$ vertices is by creating cycles from matchings and matchings from cycles.

If $\mathcal{C}$ is the set of cycles, then $|\mathcal{C}| = \frac{(2n-1)!}{2}$ and every cycle gives rise to exactly $2$ matchings by deleting every other edge.

For every matching of size $n$ we can obtain $\frac{(n-1)!}{2} \cdot 2^n$ cycles. First we arrange the $n$ edges from the matching into a cycle, as if they were vertices. There are $\frac{(n-1)!}{2}$ ways of arranging them in such a manner. If we now re-expand them into edges then we have $2$ choices for every edge on how we want to orient it when connecting, giving $2^n$ options per arrangement of a matching.

With $\mathcal{M}$ the set of the matchings we have $$ 2 |\mathcal{C}| = \frac{(n-1)!}{2} \cdot 2^n |\mathcal{M}| \\ \implies |\mathcal{M}| = \frac{(2n-1)!}{(n-1)!}\cdot\frac{2}{2^n}\cdot\frac{n}{n} = \frac{(2n)!}{2^nn!} $$

$\endgroup$
-6
$\begingroup$

Gerry was correct (sort of) in his first statement, saying that it is the number of ways to partition the six vertices into three sets of two. However, the answer of number of perfect matching is not 15, it is 5. In fact, for any even complete graph G, G can be decomposed into n-1 perfect matchings. Try it for n=2,4,6 and you will see the pattern.

Also, you can think of it this way: the number of edges in a complete graph is [(n)(n-1)]/2, and the number of edges per matching is n/2. What do you have left for the number of matchings? n-1.

$\endgroup$
1
  • 2
    $\begingroup$ I think these are all perfect matchings for 6: 12-34-56, 12-35-46, 12-36-45, 13-24-56, 13-25-46, 13-26-45, 14-23-56, 14-25-36, 14-26-35, 15-23-46, 15-24-36, 15-26-34, 16-23-45, 16-24-35, 16-25-34. That's 15, not 5. $\endgroup$ Dec 13, 2014 at 5:14

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.