Question

What is the number of perfect matching of a complete graph Kn with n vertices?

Answer 1

Answer on Question#38338 – Math - Discrete Mathematics

A perfect matching, every vertex of the graph is incident to exactly one edge of the matching. A perfect matching is, therefore, a matching of a graph containing $\frac{n}{2}$ edges; the largest possible, meaning perfect matchings are only possible on graphs with an even number of vertices. A perfect matching is sometimes called a complete matching or 1-factor.

The number of perfect matchings of the complete graph $K_n$ is given by the double factorial $(n - 1)!!$

What means double factorial?

- In mathematics, the product of all the odd integers up to some odd positive integer $n$ is called the double factorial or odd factorial of $n$, and denoted by $n!!$

For example, $9!! = 1 \times 3 \times 5 \times 7 \times 9 = 945$.