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

44 votes

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

Correct Answer: $A$

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

Correct Answer: $A$

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 K_{6} 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...**

3

@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

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?

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

21

**Edited:**

$1^{st}$ edge, 5 ways (take 1-2)

$2^{nd}$ edge, 3 ways (take 3-4)

$3^{rd}$ edge, 1 way (take 5-6)

$5\times 3\times 1=15$

**Original:**

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

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

7

Is there any difference between Perfect and Maximum Matching.?

They are not related. Give it a proper read from Rosen.

Maximal matching : we cannot add any edge to current set of edge to satisfy matching property.

Maximum matching : Maximum among all maximal.

perfect matching : one of the matching in which all vertices are covered.

2

Imagine a world with $6$ people.

Assume a graph, where each person is a vertex and there's an edge between two vertices, if the two persons representing the vertices like each other.

So, the question represents a scene where everyone loves everyone else, and there's no conflicts of gender whatsoever (because the graph is complete, and not bipartite).

We, the gods, as a wedding planner, have a job to unite those who like each other. If we do our job perfectly, there's no lonely person in the end, and every person is married to exactly one person. We call it a "perfect matching".

If everyone likes everyone else, then it's very easy for us.

We pick first candidate to marry, there's $6$ choices for that.

Now, we pick second candidate to marry the first one we picked, there's $5$ choices for that.

So, total possible matches are $6 \times 5 = 30$

But, who we picked first, and who we picked second doesn't matter, because in the end, they're going to be the same couple.

So, total possible matches will be $ = \frac{30}{2} = 15$

Assume a graph, where each person is a vertex and there's an edge between two vertices, if the two persons representing the vertices like each other.

So, the question represents a scene where everyone loves everyone else, and there's no conflicts of gender whatsoever (because the graph is complete, and not bipartite).

We, the gods, as a wedding planner, have a job to unite those who like each other. If we do our job perfectly, there's no lonely person in the end, and every person is married to exactly one person. We call it a "perfect matching".

If everyone likes everyone else, then it's very easy for us.

We pick first candidate to marry, there's $6$ choices for that.

Now, we pick second candidate to marry the first one we picked, there's $5$ choices for that.

So, total possible matches are $6 \times 5 = 30$

But, who we picked first, and who we picked second doesn't matter, because in the end, they're going to be the same couple.

So, total possible matches will be $ = \frac{30}{2} = 15$

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

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?

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

1 vote

No. of perfect matchings in a complete graph $K_{2n}$ =

Please note it is for $K_{2n}$ and not $K_{n}$.

Here, 2n = 6.

So, $\frac{6*5*4*3*2}{3*2*8}=15$

As for Cyclic graphs $C_n$

Two matchings if n is even, none otherwise.

https://math.stackexchange.com/questions/1981111/number-of-distinct-perfect-matchings-in-a-cycle

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

* *

0 votes

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

0 votes

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

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