GATE CSE 2003 | Question: 36

Question

How many perfect matching are there in a complete graph of $6$ vertices?

• A. $15$
• B. $24$
• C. $30$
• D. $60$

Comments

For first perfect matching no of options = 5
For 2nd  perfect matching no of options = 3 (two vertexes are already used)
For third perfect matching no of options = 1( 4 vertices are already used)
so total = 5 * 3 * 1 = 15

---

good one

Answer 1

Perfect matching of 1-factor means that edges have to be selected such that no two edges have same vertices and all the vertices have to be covered in the perfect matching set. 

Hence, for the given question, there can be 6C2 *  4C2 * 2C2 = 90     Now, the three pairs selected have the same order, hence 90/3! = 15. So option A is the answer