The Gateway to Computer Science Excellence
First time here? Checkout the FAQ!
x
+31 votes
3.6k 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.6k points)
edited by | 3.6k views
+1
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

6 Answers

+49 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 $=\frac{90}{3!}= \frac{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\times 3=15.$
answered by Veteran (359k points)
edited by
0

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...
 

+2

@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 .

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

Why did you divide the result by 3! in the first method and not in the second method?
0
Sir, can you please elaborate more on why to divide by 3! ?

and how can we apply the same approach for a complete graph with 4 vertices?
+1

@charul  "Choosing 3 players from 4 distinct players at a time" is different from choosing 1 player from 4 and then choosing 1 player from remaining 3 and then choosing 1 player from remaining 2 and then choosing 1 player from remaining 1 .... 

In  2nd case you will see more possibilities ... so to tally that we divide .. 

+6
\begin{align} \#\text{Perfect matchings of $K_{2n}$} &= (2n-1)(2n-3)(2n-5)\cdots 5.3.1\\ &=\dfrac{(2n)(2n-1)(2n-2)(2n-3)\cdots 5.4.3.2.1}{(2n)(2n-2)\cdots4.2}\\ &=\dfrac{(2n)!}{(2*n)(2*(n-1))\cdots(2*2)(2*1)}\\ &= \bbox[yellow,5px,border: 2px solid red]{\dfrac{(2n)!}{2^n\times n!}} \end{align}
0
Hi Arjun Sir,

 

Is there any difference between Perfect and Maximum Matching.? Please clarify.  If we consider N is even.
0

Abhijit Sen 4 maximal or maximum?

+31 votes

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

The complete graph $k_{n}$ have a perfect matching only when n is even. So let $n=2m.$ 

Let the vertices be $V_{1} , V_{2},\ldots ,V_{2m}$.    

$v_{1}$ can be joined to any other $\left(2m-1\right)$ vertices.

$v_{2}$ can be joined to any other $\left(2m-3\right)$ vertices.

Similarly, go till $V_{2m}$ which will have only one vertex to be joined with.

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

In the above question $2m=6.$

So, No. of perfect matches = $5\times 3\times 1=15.$

answered by Junior (551 points)
edited by
0

"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? 

0
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.. :)
+14 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 Boss (30.7k points)
edited by
+1
how 15 ?
0
2n = 6,

n = 3

@Amar, Please update the answer !
+1

Updated.

+3 votes

Answer is A ..

answered by Boss (11.4k points)
+1

This might help ...

+1

This one ....

+1 vote

Perfect matching is matching if every vertex is matched vertex ,We can solve it easily by (2n)! /2n n!  = Numer of perfect matching 

Number of perfect matching = 6!/23 * 3! = 15 so option a

answered by Loyal (6.9k points)
0 votes

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

 

 

  

answered by (93 points)


Quick search syntax
tags tag:apple
author user:martin
title title:apple
content content:apple
exclude -tag:apple
force match +apple
views views:100
score score:10
answers answers:2
is accepted isaccepted:true
is closed isclosed:true

41,079 questions
47,675 answers
147,469 comments
62,393 users