a.
(1999 Test 1 Problem 7(b)) See the solution above.

b.
(1999 Test 1 Problem 7(d) simplified) We give an alternative proof for this simpler version. We prove that there is a $\Delta_G$-colouring by induction on the number $n$ of vertices.

The base case is $n = 3$, and the graph is $A - B - C$. Clearly, we can assign colour 1 to $A$ and $C$, and colour 2 to $B$. This gives $\chi_G \leq 2 = \Delta_G$.

Assume the assertion holds when there are fewer than $n$ vertices. Consider a simple connected graph $G$ with $n$ vertices which is not regular. Since it is not regular, there is a vertex $A$ having degree at most $\Delta_G - 1$. Let $G_1, G_2, \dots, G_m$ be the connected components of $G - \{A\}$. We claim that there is a $\Delta_G$-colouring for each $G_j$.

Suppose on the contrary that $G_1$ has no $\Delta_G$-colouring. By the inductive hypothesis, $G_1$ must be regular. If $\Delta_{G_1} \leq \Delta_G - 1$, then by part (a), we have
$$\chi_{G_1} \leq \Delta_{G_1} + 1 \leq \Delta_G.$$

This shows a $\Delta_G$-colouring exists. Therefore, we may assume $\Delta_{G_1} = \Delta_G$. But then this implies all vertices in $G_1$ has degree $\Delta_G$. This is impossible since one of these vertices is adjacent to $A$, and hence its degree in $G$ is at least $\Delta_G + 1$. This proves our claim.

Now, we choose any $\Delta_G$-colouring for each $G_j$. Lastly, we can assign a colour to $A$ which is different from the colours of all its neighbours since $\deg A \le \Delta_G - 1$. This completes the proof by induction.