A short proof of the middle levels theorem

Petr Gregor, Torsten Mütze, Jerri Nummenpalo

Consider the graph that has as vertices all bitstrings of length $2n+1$ with exactly $n$ or $n+1$ entries equal to 1, and an edge between any two bitstrings that differ in exactly…