# Matching, colouring and planarity: GATE CS question with solution

From the GATE Daily set of 26 October 2026, question 3 of 10 (https://gatedaily.in/q/2026-10-26-matchings-in-cycle-on-nine-vertices/). Difficulty: hard.

### Q.3 · Discrete Mathematics · Matching, colouring and planarity · NAT, 2 marks (answer with a number)

A *matching* in an undirected graph is a set of edges in which no two edges share an endpoint; the empty set of edges is also a matching.

Let $C_9$ be the cycle on the 9 vertices $v_1, v_2, \dots, v_9$, with the 9 edges $v_1v_2, v_2v_3, \dots, v_8v_9$ and $v_9v_1$.

The number of matchings in $C_9$ is ______.

(Answer in integer)

**Answer:** 76

**Solution.** **Method: reduce the cycle to paths, then use the path recurrence.**

*Paths first.* Let $p(n)$ be the number of matchings (including the empty one) of a path on $n$ vertices. Look at the last vertex: either it is unmatched (the rest is a path on $n-1$ vertices) or it is matched to its only neighbour (remove both, leaving a path on $n-2$ vertices). So

$$p(n) = p(n-1) + p(n-2),\quad p(1) = 1,\ p(2) = 2.$$

This gives $p = 1, 2, 3, 5, 8, 13, 21, 34, 55$ for $n = 1, \dots, 9$.

*Now the cycle.* Pick the closing edge $e = v_9v_1$.

- Matchings **without** $e$: these are exactly the matchings of the path $v_1v_2\cdots v_9$, so $p(9) = 55$.
- Matchings **with** $e$: $v_9$ and $v_1$ are used up, and the rest is any matching of the path $v_2 \cdots v_8$ on 7 vertices, so $p(7) = 21$.

Total: $55 + 21 = 76$.

**Cross-check by size.** A cycle on $n$ vertices has $\frac{n}{n-k}\binom{n-k}{k}$ matchings of size $k$. For $n = 9$: $k = 0,1,2,3,4$ give $1, 9, 27, 30, 9$, which sum to 76.

**Trap.** Treating $C_9$ as a path gives 55 (the closing edge is ignored); using a path on 8 vertices gives 34; leaving out the empty matching gives 75.

**What was tested:** splitting on one edge to turn a cycle into paths, and the Fibonacci recurrence for matchings in a path.

**Remember:** To count matchings in a cycle, split on one edge: matchings that avoid it are matchings of a path on n vertices; matchings that use it are matchings of a path on n - 2 vertices.