GATE CS 2026 Set 1 Q47 — Graphs: Connectivity, Matching, Colouring

Let $M(n)$ denote the number of matchings in a path graph $P_n$ with $n$ vertices.

We can establish a recurrence relation for $M(n)$ by considering the last vertex $v_n$ in the path $v_1 - v_2 - \dots - v_n$:

• Case 1: $v_n$ is not matched. The remaining $n-1$ vertices can be matched in $M(n-1)$ ways.
• Case 2: $v_n$ is matched. It must be matched with its only neighbor $v_{n-1}$. The remaining $n-2$ vertices can be matched in $M(n-2)$ ways.

Thus, we obtain the recurrence relation:

The base cases are:

• $M(1) = 1$ (the empty matching $\emptyset$ on a single vertex)
• $M(2) = 2$ (the empty matching and the single-edge matching on two vertices)

Using the recurrence, we compute the values sequentially:

• $M(3) = M(2) + M(1) = 2 + 1 = 3$
• $M(4) = M(3) + M(2) = 3 + 2 = 5$
• $M(5) = M(4) + M(3) = 5 + 3 = 8$
• $M(6) = M(5) + M(4) = 8 + 5 = 13$
• $M(7) = M(6) + M(5) = 13 + 8 = 21$
• $M(8) = M(7) + M(6) = 21 + 13 = 34$

Therefore, the number of matchings in a path on $8$ vertices is 34.