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

A matching in a graph is a set of edges without common vertices (including the empty set).

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

To find a recurrence relation for $M(n)$:

1. If the last edge $(v_{n-1}, v_n)$ is not included in the matching, the number of valid matchings is $M(n-1)$.

2. If the last edge $(v_{n-1}, v_n)$ is included in the matching, no other edge incident to $v_{n-1}$ can be chosen, leaving $M(n-2)$ valid matchings on the remaining $n-2$ vertices.

Thus, the recurrence is:

Base cases:

• $M(0) = 1$ (empty path has $1$ matching: the empty set)

• $M(1) = 1$ ($1$ vertex has $1$ matching: the empty set)

• $M(2) = 2$ ($1$ edge: empty set or the edge itself)

Computing the values iteratively (which gives the Fibonacci numbers $F_{n+1}$ where $F_1 = 1, F_2 = 1, F_3 = 2, \dots$):

• $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$

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