MathOverflow is a question and answer site for professional mathematicians. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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|cite|improve this question
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|cite|improve this answer

Your Answer

 
discard

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.