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 Q(d) can be extended to a Hamiltonian cycle of Qd. We [Jiri 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 X(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(K(n,n)) of a complete bipartite graph is bipartite if and only if n is even or n = 1. We prove that M(K(n,n)) is connected for n even and M(K(n,n)) has two components for n add, n >= 3. We also compute distances between perfect matchings in M.(K(n,n)) (C) 2009 Elsevier Ltd. All rights reserved.