Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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.

share|cite|improve this question
up vote 7 down vote accepted

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

share|cite|improve this answer
Side note. For a general complete graph on $2n$ vertices, this number comes out to be $\frac{(2n)!}{n! 2^{n}}$. – Srivatsan Aug 31 '11 at 11:19
In other words, it's the product of the odd numbers up to the number of vertices. – becko Sep 1 '12 at 20:13
Or even for $\#V = 2n$ we have $(2n - 1)!!$ perfect matchings. – Aurélien Ooms May 17 '14 at 10:22
@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 – PardonMeForMySuperPoorMaths Dec 11 '14 at 19:15
@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)!)$. – Gerry Myerson Dec 11 '14 at 22:00

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

share|cite|improve this answer

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.

share|cite|improve this answer
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. – Gerry Myerson Dec 13 '14 at 5:14

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

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