edited by
44,974 views
60 votes
60 votes

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

  1. $15$
  2. $24$
  3. $30$
  4. $60$
edited by

9 Answers

Best answer
83 votes
83 votes
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$
edited by
50 votes
50 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.$

edited by
24 votes
24 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.

edited by
2 votes
2 votes

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

$$\frac{(2n)!}{n! 2^n}$$

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.


Sources: https://math.stackexchange.com/questions/60894/how-to-find-the-number-of-perfect-matchings-in-complete-graphs

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

Answer:

Related questions

65 votes
65 votes
9 answers
1
Kathleen asked Sep 17, 2014
15,480 views
A graph $G=(V,E)$ satisfies $\mid E \mid \leq 3 \mid V \mid - 6$. The min-degree of $G$ is defined as $\min_{v\in V}\left\{ \text{degree }(v)\right \}$. Therefore, min-d...
65 votes
65 votes
5 answers
2
3 votes
3 votes
0 answers
3
admin asked Dec 15, 2022
372 views
Count the number of perfect matchings in the bipartite graph whose adjacency matrix $\text{A}$ is as follows.\[\left[\begin{array}{lll}1 & 1 & 0 \\0 & 1 & 1 \\1 & 1 & 1\e...
4 votes
4 votes
2 answers
4