Past exam of the probability, statistics and options I course of the University of Oxford / 2009 / R / 1 (R1)

Label the outer square $000,001,011,010$ in cyclic order and the inner square $100,101,111,110$ in corresponding order. Join corresponding vertices radially. Each edge changes exactly one bit, so this gives every edge of $Q_3$, with no crossings.

Partition the vertices by the parity of the number of one-bits. Every edge reverses that parity, giving a two-colouring; at least two colours are needed because an edge exists. Therefore the vertex chromatic number is two.

Every vertex has degree three, so its incident edges require three distinct colours. Three suffice by colouring an edge according to which of the three coordinates changes; every vertex has exactly one edge of each coordinate type. Thus the edge chromatic number is three.

The three faces incident to any cube vertex are pairwise adjacent along edges, forcing three colours. Three suffice by giving each pair of opposite faces a common colour, using a different colour for each of the three pairs. Hence the face chromatic number is three.

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.

The hypercube is connected: successive coordinate flips reach any target bit string. Every vertex has degree $k$. A finite connected graph has an Euler circuit exactly when all vertex degrees are even. Therefore

If the printed $K_{33}$ means an ordinary $K_{3,3}$ subgraph, the claim is false. Any two distinct hypercube vertices have exactly two common neighbors when their Hamming distance is two, and no common neighbors otherwise. Three common neighbors, required by any pair of vertices on one side of $K_{3,3}$, are therefore impossible.

The valid intended statement is a graph subdivision of $K_{3,3}$. An explicit one in $Q_4$ has branch sets $A=\{0000,0011,1100\}$ and $B=\{0001,0010,0100\}$. Six of the nine branch-to-branch connections are direct edges: $0000$ joins all three vertices of $B$, $0011$ joins $0001,0010$, and $1100$ joins $0100$. The other three paths areEvery step changes one bit and the six internal vertices are distinct and are not branch vertices. Thus these paths and direct edges form the required topological subgraph. For $k>4$, append $k-4$ zeros to every label, embedding the construction in $Q_k$.

The square $Q_2$ and the drawn cube $Q_3$ are planar. For $k\ge 4$, the subdivision in part (v) prevents planarity by Kuratowski's theorem. One can also check the edge count directly: a triangle-free simple planar graph with $n\ge 3$ vertices has at most $2n-4$ edges, whereas $Q_k$ has $n=2^k$ and $m=k{2}^{k-1}\ge 2n$. Thus