Matching, colouring and planarity: GATE CS question with 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

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_9{v}_1$.

• Matchings without $e$: these are exactly the matchings of the path $v_1{v}_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}\left(\genfrac{}{}{0ex}{}{n-k}{k}\right)$ 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.