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\geq 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\geq 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\}$. 



Is every matching of the hypercube graph extensible to a Hamiltonian cycle
This is a known open problem. See "[Matchings extend to Hamiltonian cycles in hypercubes](http://garden.irmacs.sfu.ca/?q=op/matchings_extends_to_hamilton_cycles_in_hypercubes)" over at the Open Problem Garden.


