Abstract. The [Formula: see text]-dimensional hypercube graph [Formula: see text] has as vertices all subsets of [Formula: see text], and an edge between any two sets that differ in a single element. The Ruskey–Savage conjecture asserts that every matching of [Formula: see text], [Formula: see text], can be extended to a Hamilton cycle, i.e., to a cycle that visits every vertex exactly once. We prove that every matching of [Formula: see text], [Formula: see text], can be extended to a cycle that visits at least a [Formula: see text]-fraction of all vertices.

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.