revolving door conjecture

The middle levels conjecture (Havel 1983, Buck and Wiedemann 1984), also known as revolving door conjecture, posits that the middle layer graph of order n has a Hamilton cycle for every n>=1. The conjecture was proved by Mütze; see also Mütze. Since the middle layer graphs are vertex-transitive, proving the conjecture established that these graphs are not counterexamples to Thomassen's conjecture on nonhamiltonian vertex-transitive graphs. Knuth gave the middle levels conjecture the highest difficulty rating (49/50) among all open problems in his book.

Hamiltonian cycle | middle layer graph | vertex-transitive graph