Connectivity of Matching Graph of Hypercube
Jiří Fink · SIAM Journal on Discrete Mathematics · 2009
The matching graph $\mathcal{M}(G)$ of a graph G has a vertex set of all perfect matchings of G, with two vertices being adjacent whenever the union of the corresponding perfect matchings forms a Hamiltonian cycle. We prove that the matching graph $\mathcal{M}(Q_d)$ of the d-dimensional hypercube is bipartite and connected for $d\ge4$. This proves Kreweras's conjecture [Bull. Inst. Combin. Appl., 16 (1996), pp. 87–91] that the graph $M_d$ is connected, where $M_d$ is obtained from $\mathcal{M}(Q_d)$ by contracting all vertices of $\mathcal{M}(Q_d)$ which correspond to isomorphic perfect matchings.