Matching graphs of hypercubes and complete bipartite graphs

AbstractKreweras’ 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 of Qd. 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) 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 of G. We show that the matching graph M(Kn,n) of a complete bipartite graph is bipartite if and only if n is even or n=1. We prove that M(Kn,n) is connected for n even and M(Kn,n) has two components for n odd, n≥3. We also compute distances between perfect matchings in M(Kn,n)