Question

How many perfect matchings are there in a complete graph of 10 vertices?

(a) 60

(b) 945

(c) 756

(d) 127

I got this question in homework.

This intriguing question originated from Isomorphism in Graphs in division Graphs of Discrete Mathematics

Answer 1

The correct option is (b) 945

For explanation: Perfect matching is a set of edges such that each vertex appears only once and all vertices appear at least once (exactly one appearance). So for n vertices perfect matching will have n/2 edges and there won’t be any perfect matching if n is odd. For n=10, we can choose the first edge in ^10C2 = 45 ways, second in ^8C2=28 ways, third in ^6C2=15 ways and so on. So, the total number of ways 45*28*15*6*1=113400. But perfect matching being a set, order of elements is not important and the permutations 5! of the 5 edges are same only. So, total number of perfect matching is 113400/5! = 945.