Past exam of the mathematics course of the University of Cambridge / 2009 / ii / Paper 3 / 17F / c / Solution

The first assertion is false. The complete graph $K_4$ has $\chi (K_4)=4$, but ${\chi }^{\prime }(K_4)=3$: color each of its three perfect matchings with its own color. It is connected and has more than two vertices.

The second assertion is false. Take the crown graph with bipartition $a_1,\dots ,a_5$ and $b_1,\dots ,b_5$, joining $a_i$ to $b_j$ exactly when $i\ne j$. Its chromatic number is two. In the ordering $a_1,b_1,a_2,b_2,\dots ,a_5,b_5$, the greedy coloring algorithm assigns color $i$ to both $a_i,b_i$: both see all previously used colors, but they are not adjacent to each other. It therefore uses five colors, exceeding $2\chi (G)=4$. Taking more pairs makes the ratio arbitrarily large.

The third assertion is true. When an edge is colored greedily, at most $2\Delta -2$ adjacent edges have previously received colors. Thus the greedy coloring algorithm uses at most $2\Delta -1\le 2{\chi }^{\prime }(G)-1<2{\chi }^{\prime }(G)$ colors whenever the graph has an edge. The edgeless case is trivial. This bound holds for every edge ordering.