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 QdQd can be extended to a Hamiltonian cycle of QdQd. We [Jiří Fink, Perfect matchings extend to hamilton cycles in hypercubes, J. Combin. Theory Ser. B, 97 (6) (2007) 1074–1076] proved this conjecture but here we present a simplified proof.The matching graph  M(G)M(G) of a graph GG has a vertex set of all perfect matchings of GG, with two vertices being adjacent whenever the union of the corresponding perfect matchings forms a Hamiltonian cycle of GG. We show that the matching graph M(Kn,n)M(Kn,n) of a complete bipartite graph is bipartite if and only if nn is even or n=1n=1. We prove that M(Kn,n)M(Kn,n) is connected for nn even and M(Kn,n)M(Kn,n) has two components for nn odd, n≥3n≥3. We also compute distances between perfect matchings in M(Kn,n)M(Kn,n).