Matchings in hypercubes extend to long cycles

Jiří Fink, Torsten Mütze

The $d$-dimensional hypercube graph $Q_d$ has as vertices all subsets of $\{1,\dots ,d\}$, and an edge between any two sets that differ in a single element. The Ruskey-Savage conje…