Matching graphs of Hypercubes and Complete Bipartite Graphs

Kreweras' conjecture [G. Kreweras: Matchings and Hamiltonian cycles on hypercubes, Bull. Inst. Combin. Appl. 16 (1996) 87–91] asserts that every perfect matching of the hypercube Qd can be extended to a Hamiltonian cycle. We [J. Fink: Perfect Matchings Extend to Hamilton Cycles in Hypercubes, to appear in J. Comb. Theory, Series B] proved this conjecture but here we present a simplified proof.The matching graph 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 M(Qd) of the d-dimensional hypercube is bipartite for d≥2 and connected for d≥4. This proves another Kreweras' conjecture [G. Kreweras: Matchings and Hamiltonian cycles on hypercubes, Bull. Inst. Combin. Appl. 16 (1996) 87–91] that the graph Md is connected, where Md is obtained from M(Qd) by contracting every pair of vertices of M(Qd) whose corresponding perfect matchings are isomorphic.