Graph Theory

Question

How many perfect matchings does a complete graph K(n) with even vertices have?

Is it $\frac{n!}{(2!)^{(n/2)}*(\frac{n}{2})!}$ ?

As it's like the combinatorics problem of dividing all n vertices into n/2 groups each of size 2.

OR

Is it (n-1) ?

I read that K(n) can be properly edge coloured using  (n-1) colours. If we make its monochromatic subraphs it'll give n-1 different perfect matchings.

So I am confused. Please Help!!

Answer 1

For each vertex, you need to find a pair. Lets select any one vertex. For this vertex, you can choose other pair vertex in (n-1)C₁ ways. Similarly, we do for other vertices. So,

Ans = (n-1)C₁ *  (n-3)C₁ * (n-5)C₁ *  ........ * (1)C₁

Comments

Yeah but what exactly is this (n-1) different perfect colouring thing? I read it at wikipedia:

https://en.wikipedia.org/wiki/Edge_coloring#/media/File:Complete-edge-coloring.svg

Can you provide some insights?

---

@Gate 17 aspirant. I would suggest you read the article from Graph Theory-Narsingh Deo. Its a good book. Else search it on the the net. First you need to know what is matching. Then go for it.