Number of matchings of even cycles

Here is a bijective proof.

Label the vertices of $C_{2n}$ as $1, 2, \dots, n, 1', 2', \dots, n'$ in clockwise order and let $M$ be a matching of size $k<n$ in $C_{2n}$. Since $M$ is not a perfect matching, there must exist $i$ such that both of the edges $(i, i+1)$ and $(i', (i+1)')$ are not in $M$ (note that if $i=n$, then $i+1=1'$ and $(i+1)'=1$). Choose $i$ minimum and replace the edges $(i,i+1)$ and $(i', (i+1)')$ by the edges $(i, (i+1)')$ and $(i', i+1)$. This creates two copies of $C_n$ where the numbers $1, \dots, n$ appear in each copy (although some are primed and some not). Rename all the vertices in the copy of $C_{n}$ containing $1'$ as primed vertices, and rename all the vertices in the copy of $C_{n}$ containing $1$ so that they are not primed. Note that this process is reversible, so this gives the required bijection.

This is joint work (possibly over beer) with Aurélien Ooms.


There is in fact a topological(?) proof of this statement and the following generalization, essentially due to Péter Csikvári (Section 4, Lemma 4.2).

We define a double cover (or ''2-lift'') $H$ of a graph $G$ as follows: consider $G$ as a topological space with CW structure, and $\pi:H\to G$ is a topological double cover with CW structure induced from $G$. Let $G\sqcup G$ denote the disconnected double cover of $G$. Let $m_k(G)$ denote the number of $k$-edge matchings in $G$.

Prop. Let $G$ be a graph with no cycle of length smaller than $g$ (e.g. let $g$ be the girth of $G$) and let $H$ be a double cover of $G$. Then for any $k < g$, $$m_k(H) = m_k(G\sqcup G) .$$

Proof: Consider a $k$-matching $M\subset H$, and consider its image $\pi(M)$ in $G$. The image has vertices of valence at most 2, so $\pi(M)$ is a disjoint union of paths and cycles. But since $k<g$, there are no cycles. Finally, observe that any path in $G$ lifts to a matching in $H$ in exactly two ways, where $H$ is any double cover. Since $G\sqcup G$ is a double cover, the result follows.


Csikvári observed that when $G$ is bipartite, the same type of argument, now accounting for (even) cycles, implies that $$m_k(H) \leq m_k(G\sqcup G) $$ for any size matching $k$. This is used to prove tight lower bounds on the number of matchings in a bipartite, $d$-regular graph.