A note on the middle levels problem

The middle levels problem consists in determining a hamiltonian cycle in the bipartite Kneser graph B ( 2 k + 1 , k ) , also known as the middle levels graph and denoted by B k . Previously, it was proved that a particular hamiltonian path in a reduced graph of B k implies a hamiltonian cycle in B k and a hamiltonian path in the Kneser graph K ( 2 k + 1 , k ) . We show that the existence of such a particular hamiltonian path in a reduced graph of K ( 2 k + 3 , k ) implies a hamiltonian path in K ( 2 k + 3 , k ) for k ź 1 or 2 ( mod 3 ) . Moreover, we utilize properties from the middle levels graphs to improve a known algorithm speeding up the search for such a particular hamiltonian path in the reduced graph of B k .