Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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|improve this question
add comment

1 Answer

up vote 4 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|improve this answer
5  
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
2  
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 at 10:22
add comment

Your Answer

 
discard

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.