Correct : 34

What is a Matching?
A matching in a graph is a set of edges where no two edges share a common vertex. Keep in mind that an empty set (0 edges) is also considered 1 valid matching.
Finding the Recurrence Relation
Let M(n) be the number of matchings for a path graph with n vertices. If we look at the very last edge of the path (connecting vertex n-1 to vertex n), we have two choices:
- Don''t use the last edge: The number of matchings is the same as a path with n-1 vertices, which is M(n-1).
- Use the last edge: This covers vertices n and n-1, meaning we can''t use any other edges connected to them. The remaining matchings must come from the remaining n-2 vertices, which is M(n-2).
Adding these two choices together gives us a famous formula: M(n) = M(n-1) + M(n-2).
This is exactly the Fibonacci sequence!
Calculating up to 8 Vertices
Let''s find the base cases and build up to n = 8:
- M(1): 1 vertex, 0 edges. Only the empty matching exists. M(1) = 1.
- M(2): 2 vertices, 1 edge. The empty matching and the 1 edge itself. M(2) = 2.
- M(3): M(2) + M(1) = 2 + 1 = 3
- M(4): M(3) + M(2) = 3 + 2 = 5
- M(5): M(4) + M(3) = 5 + 3 = 8
- M(6): M(5) + M(4) = 8 + 5 = 13
- M(7): M(6) + M(5) = 13 + 8 = 21
- M(8): M(7) + M(6) = 21 + 13 = 34
There are exactly 34 possible matchings.
Correct Answer: 34