The kcube Qk has 2k vertices given by V Qk x1 xk xi 0

The k-cube Q_k has 2^k vertices given by V (Qk) = {(x₁, . . . , x_k) : x_i = 0 or 1} and an edge connecting two vertices (x₁, . . . , x_k) and (x_1\',..., x_k\' ) if and only if these vertices differ in exactly one coordinate. For which values of k is Q_k planar?

Solution

The chromatic number is 2 since Qk is bipartite. This is not dicult to see since the vertices are labeled with sequences of k 0s and 1s. One set will be the sequences with an even number of 1s and the other set will be the sequences with an odd number of 1s. There will never be an edge between two sequences with an even number of 1s (or an odd number of 1s) because edges (u,v) in the graph Qk exist only if the number of 1 in u is one more or one less than in v.