Generate (almost-)perfect matchings of the complete graph

A perfect matching of the complete graph $K_n$, $n=2m$, is a set of $m$ edges, no two of which share an end vertex. An almost-perfect matching of the complete graph $K_n$, $n=2m+1$, is a set of $m$ edges, no two of which share an end vertex. The unique vertex that is not end vertex of any edge is called unmatched (colored red in the output). The two sets of objects can be mapped onto each other by the bijection that removes a fixed vertex (colored lightblue). The inverse operation is to add a vertex and a matching edge that connects it to the previously unmatched vertex.

The algorithm running on this website generates the matchings in Gray code order. Specifically, any two consecutive perfect matchings differ by a 2-flip, i.e., two matching edges $(v,w)$ and $(v',w')$ are removed and replaced by two new edges that pair up the 4 end vertices in a different way (either $(v,v')$ and $(w,w')$, or $(v,w')$ and $(w,v')$). Under the aforementioned bijection between perfect matchings and almost-perfect matchings that removes a fixed vertex, every 2-flip that involves this removed vertex translates to a 1-flip, i.e., one matching edge $(v,w)$ is removed and replaced either by the edge $(v,u)$ or $(w,u)$, where $u$ is the previously unmatched vertex. Equivalently, in a 2-flip we take the symmetric difference with a 4-cycle, and in a 1-flip we take the symmetric difference with a 2-path. Our algorithm produces a listing of all almost-perfect matchings of $K_n$, $n=2m+1$, by 1-flips. Consequently, by applying the inverse of the aforementioned bijection, we also obtain from it a listing of all perfect matchings of $K_{n+1}=K_{2(m+1)}$ by 2-flips that all involve the same fixed vertex.

The number of perfect matchings of $K_n$, $n=2m$, and the number of almost-perfect matchings of $K_{n-1}$, are both given by the double factorials of the odd numbers $(2m-1)!!=(2m-1)(2m-3)\cdots 3\cdot 1$ (OEIS A001147).

[Zipped C source code (GNU GPL)]