number of perfect matching in complete graph

Question

Is there a way to find no of perfect matchings in a complete graph Kn where n could be either even or odd..?

Answer 1

if n is odd then perfect matching 0. because in perfect matching degree of each vertex must be 1, which is not possible if n is odd.

and if n is even then num of perfect matching in $K_{2n}=\dfrac{(2n!)}{( 2^n  *  n! )}$

Comments

explain how  K2n=( 2n! ) / ( 2^n  *  n! )

---

\begin{align} \#\text{Perfect matchings of $K_{2n}$} &= (2n-1)(2n-3)(2n-5)\cdots 5.3.1\\ &=\dfrac{(2n)(2n-1)(2n-2)(2n-3)\cdots 5.4.3.2.1}{(2n)(2n-2)\cdots4.2}\\ &=\dfrac{(2n)!}{(2*n)(2*(n-1))\cdots(2*2)(2*1)}\\ &= \bbox[yellow,5px,border: 2px solid red]{\dfrac{(2n)!}{2^n\times n!}} \end{align}

Answer 2

For Kn

if n is odd , then there is no perfect matching.

n is even then you can count it like ->

(n-1) (n-3) (n-5)...1 (This will end in 1 as n is even).

Answer 3

$\underline{\textbf{Objective}}:$ Find number of perfect matchings in $K_{n}$

$\underline{\textbf{Definition}}:$ Given graph $G = (V,E)$, a perfect matching in graph $G$ is a subset $M$ of edge set $E$, such that $\forall_{v \in V} \exists_{u \in V-v} \exists_{p \in V-u-v}\ (v,u) \in M \land (v,p) \not \in M \land (u,p) \not \in M$     

$\underline{\textbf{Observations}}:$ 

1. $^{n}C_2$ total edges in $K_{n}$
2. For perfect matching we would need $\frac{n}{2}$ edges
3. We can't have fractional edges, hence when $n$ is odd, we won't have perfect matching. 
4. No two edges should have same vertex
5. All edges should cover all the vertices
6. Every vertex has degree $n-1$

$\underline{\textbf{Algorithm}}:$ 

Total Edges = nC2
For loop 1:n/2:
    Find a random edge e=(u,v) from total edges
    total edges = remove every edge incident on u and v

This is a way to find one such subset $M$. Finding the count of such subsets will give us final answer.

$\underline{\textbf{Solution}}:$

Finding first edge will take $^{^{n}C_2}C_1 = ^{n}C_2$ ways 
Total edges would now be = $^{n}C_2 - (n-2)-(n-2)-1 = ^{n}C_2 -2n +3 = ^{n-2}C_2$ 
It would be isomorphic to $K_{n-2}$

Finding second edge will take $^{n-2}C_2$ ways 
Total edges would now be = $^{n-2}C_2 - (n-2-2)-(n-2-2)-1 = ^{n-2}C_2 -2n+7 = ^{n-4}C_2$ 
and so on.

total ways of finding edges = $^{n}C_2 \times ^{n-2}C_2 \times \dots \times ^2C_2 = \prod_\limits{i=0}^{n/2-1} \ ^{n-2i}C_2 = \dfrac{n!}{2^\frac{n}{2}}$   
This accounts for order of chosen edges, but $M$ is set, order doesn't matter. So we will divide by ($\frac{n}{2}!$). 

Final Solution, when $n$ is even,
$$\dfrac{(n)!}{2^\frac{n}{2}\frac{n}{2}!}$$
perfect matchings are there.