There are several examples of interpreting the Catalan numbers as non-nesting or non-crossing matchings of some graph. My question is: Is there a family of graphs $G_1,G_2,\dotsc$ with the number of vertices growing linearly, such that the number of matchings (not complete matchings) of $G_i$ is the $i$th Catalan number? I have checked Richard Stanley's book on Catalan numbers, but such an interpretation is not there. The closest I found is a family of graphs, where one counts the number of *complete* matchings, but this is not what I am after. Edit: I thought that the linearity condition was sufficient to force nice answers, but perhaps not. Ok so there is the classical recursion for Catalan numbers, $$C_{n+1} = \sum_k C_k C_{n-k}.$$ The family of graphs should be defined such that the number of matchings is seen to satisfy the above recursion without too much work.