{c}

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 \b[the vertex <chromatic number> is two].

Solution

Past exam of the probability, statistics and options I course of the University of Oxford / 2009 / R / 1 / ii / a / Solution

 Solution (source code)