Define the chromatic polynomial $p_{G}(t)$ of a graph $G$. Show that if $G$ has $n$ vertices and $m$ edges then

$$p_{G}(t)=a_{n} t^{n}-a_{n-1} t^{n-1}+a_{n-2} t^{n-2}-\ldots+(-1)^{n} a_{0}$$

where $a_{n}=1, a_{n-1}=m$ and $a_{i} \geqslant 0$ for all $i$. [You may assume the deletion-contraction relation, provided that you state it clearly.]

Show that for every graph $G$ (with $n>0$ ) we have $a_{0}=0$. Show also that $a_{1}=0$ if and only if $G$ is disconnected.

Explain why $t^{4}-2 t^{3}+3 t^{2}-t$ is not the chromatic polynomial of any graph.