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

For first perfect matching no of options = 5 (we have to choose one vertex, and choose another vertex from remaining 5)
For 2nd  perfect matching no of options = 3 (two vertex are already used)
For third perfect matching no of options = 1( 4 vertex are already used)
total matching = 5 * 3 * 1 = 15

Answer 2

The Number of Complete Graph is perfect matching is =        (2m)! /  2^m * m !

Where m is postive number

now 6 vertice set to the 2(3)=2(m)   now calcute   6!/8 * 3! = 15 Number Of perfect Matching

 

 

  

Comments

What is m here,

is this the no. of vertices ? @Vijay Dulam

Answer 3

Answer : A

for complete graph(K 2n) , here 2n is no. of vertices

no. of perfect matching = 2n! / ((2^n) * (n!) )

so, no. of perfect matching = 6! / (2^3 * 3!) = 720 / (8 * 6) = 15

Answer 4

For perfect matching the number of edges to be selected such that no two edge are adjacent to each other.

Hence number of ways to select the edges in complete graph with 6 vertices =  6∁2 * 4∁2 * 2∁2

Now for the set of edges selected the ordering isn’t important,  hence    6∁2 * 4∁2 * 2∁2  /3!

answer is 15    option A