Past exam of the probability, statistics and options I course of the University of Oxford / 2009 / R / 1 / iii / Solution

A vertex is a bit string of length $k$, and adjacent vertices differ in one coordinate. Therefore the parity of the number of one-bits changes along every edge. The even-parity and odd-parity strings are a bipartition, proving $Q_k$ is bipartite for every $k\ge 1$, in particular for the requested range.