search
Log In
1 vote
1.1k views

in Graph Theory 1.1k views

2 Answers

4 votes
 
Best answer

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
0
Can u explain what a perfect matching is?

What if number of vertices is an ODD number?
4

Perfect matching of a graph is a matching in which degree of each vertex is exactly one.

Why it is not possible for ODD number of vertices ? I think we can prove it by handshaking lemma, we know that $\sum degree of vertices = 2* edges$

Since each vertex has exactly degree 1

we can write as $1*\left | V \right |=2*\left | E \right | \\ \left | E \right |=\frac{\left | V \right |}{\left | 2 \right |}$

It shows number of vertices must be even as edges should be a positive integer , hence number of vertices cannot be ODD.

For K4 no. of perfect matching  are

2 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

13 votes
2 answers
1
5.2k views
Is there a way to find no of perfect matchings in a complete graph Kn where n could be either even or odd..?
asked Dec 2, 2014 in Graph Theory dhingrak 5.2k views
0 votes
1 answer
2
422 views
When matching number and covering number are same then can we say that it is a perfect matching case?Do i need to check the elements of the set( edges in both matching and covering) also if their cardinality is same?If yes,then can someone give me an example where matching number ... number same but still it is not a perfect match?I am not able to find such a case and i think it will not exist.
asked Jun 8, 2017 in Mathematical Logic rahul sharma 5 422 views
...