GATE 2026 CS (CS1) – Question 57
Let $G$ be an undirected graph, which is a path on 8 vertices. The number of matchings in $G$ is ______. (answer in integer)
Practise this question in The GATE Grind →
Show answer and explanation
Correct answer: 34
Explanation
A path on $n$ vertices $P_n$ has $n - 1$ edges: $e_1, e_2, \dots, e_{n-1}$.
A matching in a graph is a subset of edges with no common vertices (including the empty matching of 0 edges).
Let $m_n$ denote the number of matchings in $P_n$:
- Consider the last edge $e_{n-1} = (v_{n-1}, v_n)$:
1. If $e_{n-1}$ is NOT in the matching, the matching is simply any valid matching of $P_{n-1}$. There are $m_{n-1}$ such matchings.
2. If $e_{n-1}$ IS in the matching, then edge $e_{n-2}$ cannot be chosen because it shares vertex $v_{n-1}$. The remaining matched edges must form a valid matching of $P_{n-2}$. There are $m_{n-2}$ such matchings.
Thus, the number of matchings satisfies the Fibonacci recurrence:
$$m_n = m_{n-1} + m_{n-2}$$
Base cases:
- $n = 1$ ($P_1$, 0 edges): Only the empty matching $\implies m_1 = 1$.
- $n = 2$ ($P_2$, 1 edge): Empty matching and $\{e_1\} \implies m_2 = 2$.
Computing sequentially:
- $m_3 = 2 + 1 = 3$
- $m_4 = 3 + 2 = 5$
- $m_5 = 5 + 3 = 8$
- $m_6 = 8 + 5 = 13$
- $m_7 = 13 + 8 = 21$
- $m_8 = 21 + 13 = 34$
Thus, the number of matchings in $P_8$ is 34.