Past exam of the graph theory course of the University of Oxford / 2011 / 2 / a

Choose a spanning tree of the connected graph and root it at $x$. List vertices in nonincreasing order of their distance from $x$ in this tree, breaking ties arbitrarily. The root has distance zero and is last, so $v_n=x$.

Every other vertex has a parent one step closer to the root. That parent is adjacent to it and appears later in the ordering. HenceFor a graph of one vertex the condition is vacuous and the same ordering works.

Write $\Delta =\Delta (G)$, which is at least two because $x$ has the two specified neighbours. Give $y$ and $z$ the same colour, say colour one; this is proper because they are nonadjacent.

Apply part (i) to the connected graph $G\setminus \{y,z\}$, with $x$ last. Colour its vertices greedily in the resulting order using a palette of $\Delta$ colours. Every vertex before $x$ has a neighbour later in this order, so at most $\mathrm{deg}(v)-1\le \Delta -1$ of its neighbours have already received colours. At least one palette colour is available.

When $x$ is reached, all its neighbours are coloured, but the two neighbours $y,z$ have the same colour. Thus there are at most $\mathrm{deg}(x)-1\le \Delta -1$ distinct forbidden colours. Colour $x$ with a remaining one. This constructs a proper colouring withThe common colour on the two initial vertices replaces the usual need for an uncoloured neighbour at the last greedy step.

This is greedy colouring with two precoloured neighbours.