3.5k views

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

1. $15$
2. $24$
3. $30$
4. $60$
edited | 3.5k 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

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

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

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

edited
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.. :)

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.

edited
+1
how 15 ?
0
2n = 6,

n = 3

+1

Updated.

+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