Given that Q_d is the hypercube graph of dimension d then it is a known fact (not so trivial to prove though) that given a perfect matching M of Q_d (d >= 2) it is possible to find another perfect matching N of Q_d such that M \cup N is a Hamiltonian cycle in Q_d.

The question now is - given a (non necessarily perfect) matching M of Q_d (d >= 2) is it possible to find a set of edges N such that M \cup N is a Hamiltonian cycle in Q_d.

The statement is proven to be true for d in {2,3,4}