Matchings in Hypercubes Extend to Long Cycles

The d-dimensional hypercube graph  \(Q_d\) has as vertices all subsets of  \(\{1,\ldots ,d\}\) , and an edge between any two sets that differ in a single element. The Ruskey-Savage conjecture asserts that every matching of  \(Q_d\) , \(d\ge 2\) , can be extended to a Hamilton cycle, i.e., to a cycle that visits every vertex exactly once. We prove that every matching of  \(Q_d\) , \(d\ge 2\) , can be extended to a cycle that visits at least a 2/3-fraction of all vertices.