GATE CSE
First time here? Checkout the FAQ!
x
+9 votes
1.4k views

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

  1. 15
  2. 24
  3. 30
  4. 60
asked in Graph Theory by Veteran (59.2k points)   | 1.4k views

4 Answers

+20 votes
Best answer
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 = 6$, we can choose the first edge in ${}^6C_2=15$ ways, second in ${}^4C_2= 6$ ways and third in ${}^2C_2 = 1$ way. So, total number of ways $= 15\times 6=90$. But perfect matching being a set, order of elements is not important. i.e., the $3!$ permutations of the $3$ edges are same only. So, total number of perfect matching $= 90/3!= 90/6 = 15$.

Alternatively we can also say there are 3 identical buckets to be filled from 6 vertices such that 2 should go to each of them. Now the first vertex can combine with any of the other 5 vertices and go to bucket 1- 5 ways. Now only 4 vertices remain and 2 buckets. We can take one vertex and it can choose a companion in 3 ways and go to second bucket- 3 ways. Now only a single bucket and 2 vertices remain- so just 1 way to fill the last one. So total ways=5*3=15.
answered by Veteran (286k points)  
selected by

Sir,

How is it different from the following statement from at MIT Lecture:

"When a k regular graph can be colored with exactly k colors, a remarkable thing happens – every vertex appears in every mono-chromatic sub-graph, i.e. the coloring decomposes the graph into k perfect matchings"

Considering K6 as a 5 regular graph, there will be 5 different perfect matchings (as the above statement says).

So my confusion arises here !!

Are these 5 perfect matching a part of those 15 perfect matchings 

OR

Am I getting some wrong ideas about the above quoted statement.

Please Sir Explain...
 

@Arjun how u get this 

So for n vertices perfect matching will have 3 edges and there won't be any perfect matching if n is odd.  

bold part i got .

Sorry. That's n/2, not 3. Corrected now.
@Arjun Sir

Why did you divide the result by 3! in the first method and not in the second method?
+14 votes

Note: To understand the solution please go through the definitions of perfect matching

The complete graph kn have a perfect matching only when n is even.. So let n=2m. 

Let the vertices be V1 , V2 ,......,V2m.    

v1 can be joined to any other 2m-1 vertices

v2 can be joined to any other 2m-3 vertices

Similarly go till V2m which will have only one vertex to be joined with..

No of Perfect matches= (2m-1)(2m-3)(2m-5).....(3)(1)

In the above question 2m=6

So No. of perfect matches=5*3*1=15

answered by (485 points)  
edited by

"v2 can be joined to any other 2m-3 vertices"

Let n = 4 (2m = 2x2)
Then as per the above stmnt. v2 will have only one option but actually v2 will have 2 options.. is something wrong in my understanding? 

Let v1,v2,v3,v4 be the vertices... So for v1 we need to take any of the other 3 vertices.. Now we have only two vertices left which can be joined in only one way.. Hope you understand.. :)
+3 votes

For a graph with odd number of vertices we cannot have a perfect matching.

If there are $2n$ vertices in a complete graph we can surely find a perfect matching for it.

to find perfect matching we need to group vertices of the graph into disjoint sets of 2 vertices. doing so we are able to pull out an edge from the graph which is between those 2 vertices of a set. also, the set is disjoint so pulling out an edge will select only distinct vertices each time, till all vertices are covered. 

this will give rise to n sets each of 2 vertices.

Now, the problem is reduced to a combinatorics problem of distributing $2n$ vertices into $n$ sets, each of 2 vertices. also, these $n$ sets are indistinguishable as they contain same number of elements so, counting all ways by which we can do that is given by:$$\frac{(2n)!}{(2!)^n\ n!}$$

here, $2n=6$ so, answer = 15.

answered by Veteran (27.9k points)  
edited by
how 15 ?
2n = 6,

n = 3

@Amar, Please update the answer !

Updated.

–3 votes
For complete graph of 6 vertices

Number of perfect matching= n(n-1)/2

= 6*5/2=15
answered by Active (1.1k points)  
Your formulae is wrong. It just hit here correctly by luck . Try for n =8

 Akash Kanase sir is right



Top Users Jun 2017
  1. Bikram

    3704 Points

  2. Hemant Parihar

    1484 Points

  3. junaid ahmad

    1432 Points

  4. Arnab Bhadra

    1408 Points

  5. Niraj Singh 2

    1311 Points

  6. Rupendra Choudhary

    1194 Points

  7. rahul sharma 5

    1132 Points

  8. Debashish Deka

    994 Points

  9. srestha

    932 Points

  10. Arjun

    930 Points

Monthly Topper: Rs. 500 gift card
Top Users 2017 Jun 19 - 25
  1. Bikram

    1960 Points

  2. Niraj Singh 2

    1306 Points

  3. junaid ahmad

    502 Points

  4. sudsho

    410 Points

  5. akankshadewangan24

    388 Points


23,355 questions
30,066 answers
67,371 comments
28,382 users