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.
We guarantee you’ll find the right tutor, or we’ll cover the first hour of your lesson.