retagged by
2,693 views

2 Answers

Best answer
4 votes
4 votes

Number of perfect matching in complete graph $K_{2n}= \frac{2n!}{2^{n}n!}=(2n-1)(2n-3)(2n-5)....1$

For $K_{4}= \frac{4!}{2^{2}2!}=3$

3 is the correct answer

selected by
3 votes
3 votes

Matching in a graph is Distinct set of edges.

 matching M in G is a set of pairwise non-adjacent edges; that is, no two edges share a common vertex

Types of Maching

1.Maximum:-Contain maximum no. of edges

2.Maximal:-A set when no. more edges can  be added

3.Complete matching from set v1 to set v2 such that every vertex in v1 gets matched

4.Perfect Matching :-

1.when every vertex gets matched

2.perfect matching is only possible with even number of vertices

3.No. of perfect matchings for odd number of vertices are 0.

4.No. of matching in complete graph with even number of vertices are 

(2n)!/(2^n) *(n!)

or

(2m-1) *(2m-3)*(2m-5)....1

here, n=2m=number of vertices.

Related questions

16 votes
16 votes
2 answers
1
dhingrak asked Dec 2, 2014
10,625 views
Is there a way to find no of perfect matchings in a complete graph Kn where n could be either even or odd..?
0 votes
0 votes
1 answer
2
atul_21 asked Dec 21, 2017
510 views
I am not convinced by this. Please explain or please tell me the source from where I can clear this out.
0 votes
0 votes
0 answers
3
Jaspreet Kaur Bains asked Dec 19, 2017
1,690 views
Consider complete graphs K5 and K6 . Let X5 and X6 are number of perfect matching of K5 and K6 respectively. Then X5 + X6 = ________.