Past exam of the Probability, statistics and options II course of the University of Oxford / 2008 / R / 2 / iv

Every cube vertex has degree three, so $Q_3$ is not Eulerian; it even has eight odd-degree vertices, so has no open Eulerian trail. After the four diagonals are added every vertex has degree four, and the graph remains connected. Thus $Q_3^{\prime }$ is Eulerian, by the circuit criterion proved above.

Both are Hamiltonian. A Hamiltonian cycle already in the cube isSuccessive triples differ in exactly one bit, and each of the eight vertices occurs exactly once before returning. Adding edges preserves this cycle in a graph.

Both are bipartite. Partition the vertices by parity of the number of one bits. A cube edge changes one bit and an interior diagonal changes three bits, so both types join opposite parity classes. In fact $Q_3^{\prime }$ is $K_{4,4}$: from any vertex its three cube neighbors and its opposite vertex exhaust the four vertices of opposite parity.

Yes. Colour an even-parity vertex one colour and an odd-parity vertex the other. Every cube edge changes parity, so this is a proper two-colouring. At least two colours are needed because edges exist.

No. At any cube vertex its three incident faces are pairwise adjacent along the three incident edges. They would therefore require three different colours. Equivalently the dual of the planar cube embedding contains a triangle, which obstructs a face two-colouring.