$\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}}:$
- $^{n}C_2$ total edges in $K_{n}$
- For perfect matching we would need $\frac{n}{2}$ edges
- We can't have fractional edges, hence when $n$ is odd, we won't have perfect matching.
- No two edges should have same vertex
- All edges should cover all the vertices
- 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.
For $n=6$, there are in total $15$ perfect matchings.
$\textbf{Option (A)} \text{ is correct}$.
