Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

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

share|improve this question
add comment

1 Answer 1

up vote 14 down vote accepted

This is a known open problem. See "Matchings extend to Hamiltonian cycles in hypercubes" over at the Open Problem Garden.

share|improve this answer
add comment

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.