GATE CSE 2026 Session 1 Q57: Number of matchings in a path on 8 vertices

Answer: 34 (official GATE 2026 final answer key)

Concept used: Matchings in a path satisfy a Fibonacci recurrence (the empty matching counts).

First step: Let $m_n$ be the count for $n$ vertices: either the last vertex is unmatched ($m_{n-1}$) or matched to its neighbour ($m_{n-2}$), with $m_1 = 1$, $m_2 = 2$.