GATE CS 2003 Q36 — Graphs: Connectivity, Matching, Colouring

A perfect matching in a graph of $2n$ vertices is a set of $n$ edges such that no two edges share a common vertex, and every vertex is incident to exactly one edge in the matching.

For a complete graph $K_{2n}$ with $2n$ vertices, the number of perfect matchings can be calculated step-by-step:

1. Select any arbitrary vertex. There are $2n - 1$ possible vertices to pair it with.
2. From the remaining $2n - 2$ vertices, select another arbitrary vertex. There are $2n - 3$ possible vertices to pair it with.
3. Continuing this process, the total number of perfect matchings is given by the double factorial: $$(2n - 1)!! = (2n - 1) \times (2n - 3) \times \dots \times 3 \times 1$$

For a complete graph with $6$ vertices ($2n = 6$, so $n = 3$):

Therefore, the correct option is A.