Prove that $\chi(G) \leqslant \Delta(G)+1$ for every graph $G$. Prove further that, if $\kappa(G) \geqslant 3$, then $\chi(G) \leqslant \Delta(G)$ unless $G$ is complete.

Let $k \geqslant 2$. A graph $G$ is said to be $k$-critical if $\chi(G)=k+1$, but $\chi(G-v)=k$ for every vertex $v$ of $G$. Show that, if $G$ is $k$-critical, then $\kappa(G) \geqslant 2$.

Let $k \geqslant 2$, and let $H$ be the graph $K_{k+1}$ with an edge removed. Show that $H$ has the following property: it has two vertices which receive the same colour in every $k$-colouring of $H$. By considering two copies of $H$, construct a $k$-colourable graph $G$ of order $2 k+1$ with the following property: it has three vertices which receive the same colour in every $k$-colouring of $G$.

Construct, for all integers $k \geqslant 2$ and $\ell \geqslant 2$, a $k$-critical graph $G$ of order $\ell k+1$ with $\kappa(G)=2 .$