Geodesics in a Graph of Perfect Matchings

Roy Ben-Ari

Published 2013-06-15, updated 2014-09-09Version 2

This paper studies geodesics in the graph $\mathscr{P}_{m}$, which has all perfect matchings in $K_{2m}$ as vertices with two perfect matchings connected by an edge if their symmetric difference is a cycle of length four. The diameter of $\mathscr{P}_{m}$, as well as the eccentricity of each vertex, are shown to be $m-1$. The number of geodesics between any two antipodes is shown to be $m^{m-2}$ and an explicit formula for the number of geodesics between any two matchings in $\mathscr{P}_{m}$ is given. The paper concludes by showing that the subgraph of non-crossing perfect matchings has exactly one pair of antipodes having the maximal number ($m^{m-2}$) of geodesics.