= Solution
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 <connectivity (graph theory)>[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 $\deg(v)-1\leq\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 $\deg(x)-1\leq\Delta-1$ distinct forbidden colours. Colour $x$ with a remaining one. This constructs a proper <colouring> with
$$
\boxed{\chi(G)\leq\Delta(G).}
$$
The 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>.
Back to article page
