There are 2^k distinct k-tuples of 0‘s and 1‘s. Hence the k-cube has 2^k vertices.

Consider a vertex in the k-cube and thus its associated k-tuple. Let us change exactly one of its coordinates. It has k coordinates to choose from. Hence this vertex is adjacent to k other vertices. The same applies to each vertex in the graph. Hence the k-cube has 2^k vertices each adjacent to k other vertices. Hence in total we have \frac{k2^k}{2}=k2^{k-1} edges. Note that we are dividing two in order not to double-count the edges.

Let X be the set of vertices whose associated k-tuple has an even number of 1's.

Let Y be the set of vertices whose associated k-tuple has an odd number of 1's.

We claim that (X,Y) forms a bipartition of the k-cube.

Consider two distinct vertices in X. These two vertices must differ in at least two coordinates. Same thing applies for the vertices in Y. Hence the k-cube is bipartite. \square