Extending Matchings to Gray Codes in Hypercubes with Prescribed Endpoints

A cyclic Gray code is an ordered sequence that contains all binary strings of a given length in which each consecutive string differs from the previous one in exactly one coordinate. Such a sequence directly represents a Hamiltonian cycle and path in the hypercube. Ruskey and Savage asked whether every matching in the hypercube extends to a Hamiltonian cycle, and Fink proved that every perfect matching in [Formula: see text] extends to a Hamiltonian cycle. In this study, we address a problem related to Hamiltonian paths. We prove that every matching at most in five directions where every [Formula: see text]-cycle contains at least one unsaturated vertex, can be extended to a Hamiltonian path joining two vertices in distinct partite sets of [Formula: see text], for [Formula: see text]. The only forbidden configurations are the so-called half-layers, which form certain natural obstacles.