GATE 2026 CS1 Q.57: solution and answer

GATE 2026 · CS1Q.57 · 2 marks · NAT

Let $G$ be an undirected graph, which is a path on 8 vertices. The number of matchings in $G$ is ______. (answer in integer)

See the question in the paper

Tap to open full size

Answer and solution

ANSWER

The number of matchings in a path on 8 vertices is 34.

Official answer: 34Source: Official answer key, GATE 2026 CS1 (IIT Guwahati)

Let $m_{n}$ be the number of matchings (including the empty one) in the path $P_{n}$ on $n$ vertices. $P_{1}$ has no edges, so $m_{1} = 1$ ; $P_{2}$ has one edge, so $m_{2} = 2$ (the empty matching, or the single edge).
Split on the last vertex $v_{n}$ . If $v_{n}$ is unmatched, the rest is any matching of $P_{n - 1}$ , giving $m_{n - 1}$ choices. If $v_{n}$ is matched, it must be matched to its only neighbour $v_{n - 1}$ , and the rest is any matching of $P_{n - 2}$ , giving $m_{n - 2}$ choices. The two cases are disjoint and cover everything.
So $m_{n} = m_{n - 1} + m_{n - 2}$ , a Fibonacci recurrence.
Compute: $m_{3} = 3$ , $m_{4} = 5$ , $m_{5} = 8$ , $m_{6} = 13$ , $m_{7} = 21$ , $m_{8} = 34$ .
Check by counting on edges. A matching with $k$ edges in the path $P_{8}$ (7 edges) is a choice of $k$ pairwise non-adjacent edges, which can be done in $(k 8 - k)$ ways. So the count is $(0 8) + (1 7) + (2 6) + (3 5) + (4 4) = 1 + 7 + 15 + 10 + 1 = 34$ .
The empty matching is included, because a matching is any set of pairwise non-adjacent edges, and the empty set qualifies. Both methods agree: the answer is $34$ .

KEY IDEA

Count matchings of a path with a recurrence on the last vertex: it is either unmatched or matched to its single neighbour, so $m_{n} = m_{n - 1} + m_{n - 2}$ , which gives the Fibonacci numbers. The empty matching counts.

WATCH OUT FOR

Leaving out the empty matching and answering 33, or counting only perfect matchings (which gives 1) or only maximal ones. Another slip is starting the recurrence with $m_{1} = 0$ or $m_{2} = 1$ .

From the GATE 2026 CS1 paper. Every question of this paper · Download the full paper · All 14 Graph theory questions, with notes

GATE 2026 CS1 Q.57: solution and answer

Answer and solution

More Graph theory questions