GATE CS 2026 Set 1 Q.57: Combinatorics, Counting, Recurrence Relations and Generating Functions

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

Your answer

Official answer and solution

Official answer: 34
From: Official GATE 2026 answer key

Solution

Use the Fibonacci recurrence $M_n = M_{n-1} + M_{n-2}$ for the number of matchings (independent edge sets, including the empty set) in a path graph $P_n$ on $n$ vertices.

Let $M_n$ denote the number of matchings (subsets of pairwise non-adjacent edges, including the empty matching) in a path graph $P_n$ on $n$ vertices. For the last edge $e = (v_{n-1}, v_n)$ :

Matchings that do not include $e$ correspond to matchings of $P_{n-1}$ ( $M_{n-1}$ ).
Matchings that do include $e$ cannot use $(v_{n-2}, v_{n-1})$ and correspond to matchings of $P_{n-2}$ ( $M_{n-2}$ ).

With base cases $M_1 = 1$ (empty matching) and $M_2 = 2$ (empty matching and the single edge):

M_1 = 1,\; M_2 = 2,\; M_3 = 3,\; M_4 = 5,\; M_5 = 8,\; M_6 = 13,\; M_7 = 21,\; M_8 = 34

Final answer

Common trap

Forgetting to count the empty matching $\emptyset$ (which would give 33).

The answer is the one in the official GATE answer key. The solution is this site's own explanation.

Source

Paper: GATE 2026 Computer Science and Information Technology - Session 1 (CS1)
Question: 57 of 65
Section: Computer Science and Information Technology

Report an error in this question

GATE questions are the work of the organising institutes. This site is independent and is not affiliated with them.

Question

Solution

Source