PERFECT MATCHING IN COMPLETE GRAPH

Question

Answer 1

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

Comments

Can u explain what a perfect matching is?

What if number of vertices is an ODD number?

---

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

Answer 2

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.