GATE Overflow Test Series | Discrete Mathematics | Test 4 | Question: 22

Question

Number of perfect matching in a complete graph with $8$ vertices is _________

Comments

• Pick any edge, say $\{a, b\}$ from given ${}^{8}C_{2}$ edges (in ${}^{{}^{8}C_{2}}C_{1}$ ways, which is just ${}^{8}C_{2}$ ways), now as matching is edge independent set, any edges adjacent to $\{a, b\}$ can no longer be selected. This leaves us with $K_6$.
• Repeat the process until there is no edges left to pick from: ${}^{8}C_{2} \times {}^{6}C_{2} \times {}^{4}C_{2} \times {}^{2}C_{2}$
• But as matching is a set, the order in which edges are picked does not matter, so, divide it by the number of ways to pick these four edges, $4!$

Answer 1

If n is odd, it's 0

if n is even, ans is (product of all  odd positive integer less than n)

$(n-1)\times (n-3)\times (n-5)\times... \times 1$

or you can also write as

$1 \times 3 \times 5 \times ... \times (n-1)$

So, here n = 8

7×5×3×1 = 105 is ans.

Answer 2

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.

If $n$ is even then the number of perfect matching in $K_{2m}=\dfrac{(2m!)}{( 2^m\cdot m! )};$ where $n=2m$. Here $n=2m=8\implies m = 4$

Number of perfect matching in $K_{8}=\dfrac{8!}{2^{4}\cdot 4!} = \dfrac{8\cdot7\cdot6\cdot5\cdot4!}{16\cdot 4!} = 105$.

So, the correct answer is $105$.

Answer 3

$Answer$ : $105$

This problem is same as Number of ways of partitioning the $8$ vertices into $4$ sets of two vertices each. 

Now, vertex $1$ can do partitioning with any of the $7$ vertices (say vertex $1$ and $2$). So, now our base set is reduced by $2$.

Similarly, vertex $3$ can do partitioning with any of the remaining $5$ vertices. and vertex $5$ can do partitioning with remaining $3$ vertex. 

So, number of ways of partitioning $=7\times5\times3=105$.