Status: #good
Tags: #theorem

Statement

Suppose we have graph with $2n$ vertices, and WLOG we can arrange them equidistant on a circle. We match two vertices by drawing an edge between them.

The number of non-crossing, perfect (as in, every vertex is matched) matchings on these $2n$ vertices is equal to $C_n$, the Catalan numbers.

Proof

We note that a Dyck path has $2n$ steps, so we would hope to create some bijection between this and Dyck paths to invoke the fact that the number of Dyck paths is Catalan.

Given some matching on $2n$ vertices:

1. Cut the graph so there is a line 1 through 2n (and keep the edges between them, but now they'll be curved)
2. You can make these edges directed, pointed to the right.
3. Starting from the left, at each vertex:
   1. if the edge connected to that vertex is a tail (as in, the edge points away from / starts at that vertex), then add an up step.
   2. Otherwise, the edge connected to it is a head, and we go down.
      

And to construct its inverse, you can kind of reverse the process:

1. If you see an up step, draw an open arc starting at that vertex
2. If you see a down step, take the bottommost open arc and close it at that vertex.

Alternatively, you can match horizontal lines drawn at the middle of each edge: