How many perfect matchings are there in a complete graph of 6 vertices? A. 15 B. 24 C. 30 D. 60

GATE 2003 · Discrete Mathematics · Graph Matching · medium

Answer: 15 (Option A)

1. Apply the perfect matchings formula for K_{2m}: K_6 has n = 6 = 2*3, so m = 3. Number of perfect matchings = (2*3 - 1)!! = 5!! = 5 * 3 * 1 = 15.
2. Match against options: 15 corresponds to option A.