(a) State Brooks' theorem concerning the chromatic number $\chi(G)$ of a graph $G$. Prove it in the case when $G$ is 3-connected.

[If you wish to assume that $G$ is regular, you should explain why this assumption is justified.]

(b) State Vizing's theorem concerning the edge-chromatic number $\chi^{\prime}(G)$ of a graph $G$.

(c) Are the following statements true or false? Justify your answers.

(1) If $G$ is a connected graph on more than two vertices then $\chi(G) \leqslant \chi^{\prime}(G)$.

(2) For every ordering of the vertices of a graph $G$, if we colour $G$ using the greedy algorithm (on this ordering) then the number of colours we use is at most $2 \chi(G)$.

(3) For every ordering of the edges of a graph $G$, if we edge-colour $G$ using the greedy algorithm (on this ordering) then the number of colours we use is at most $2 \chi^{\prime}(G)$.