Extending perfect matchings to Gray codes with prescribed ends (Q1648667)

Summary: A \textit{binary (cyclic) Gray code} is a (cyclic) ordering of all binary strings of the same length such that any two consecutive strings differ in a single bit. This corresponds to a Hamiltonian path (cycle) in the hypercube. Fink showed that every perfect matching in the \(n\)-dimensional hypercube \(Q_n\) can be extended to a Hamiltonian cycle, confirming a conjecture of Kreweras. In this paper, we study the ``path version'' of this problem. Namely, we characterize when a perfect matching in \(Q_n\) extends to a Hamiltonian path between two prescribed vertices of opposite parity. Furthermore, we characterize when a perfect matching in \(Q_n\) with two faulty vertices extends to a Hamiltonian cycle. In both cases we show that for all dimensions \(n\geq 5\) the only forbidden configurations are so-called half-layers, which are certain natural obstacles. These results thus extend Kreweras' conjecture with an additional edge, or with two faulty vertices. The proof for the case \(n=5\) is computer-assisted.