Matchings in Hypercubes Extend to Long Cycles

. The \ (d\) -dimensional hypercube graph \ (Qd\) has as vertices all subsets of \ (\1, , d\\), and an edge between any two sets that differ in a single element. The Ruskey–Savage conjecture asserts that every matching of \ (Qd\), \ (d 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 \ (Qd\), \ (d 2\), can be extended to a cycle that visits at least a \ (2/3\) -fraction of all vertices. KeywordshypercubecyclematchingMSC codes05C3805C7005C45