{c}

\b[True.] Represent a vertex of $Q_4$ by a four-bit string, with an edge changing exactly one bit. Color according to the parity of the sum of the bits. Every edge joins opposite parities, giving a proper two-coloring. Since the graph has edges, one color is impossible, so $\chi(Q_4)=2$.


Solution

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

 Solution (source code)