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$ and $a_{n-1}=m$ and $a_{i} \geqslant 0$ for all $0 \leqslant i \leqslant n$. [You may assume the deletion-contraction relation, provided it is clearly stated.]

Show that if $G$ is a tree on $n$ vertices then $p_{G}(t)=t(t-1)^{n-1}$. Does the converse hold?

[Hint: if $G$ is disconnected, how is the chromatic polynomial of $G$ related to the chromatic polynomials of its components?]

Show that if $G$ is a graph on $n$ vertices with the same chromatic polynomial as $T_{r}(n)$ (the Turán graph on $n$ vertices with $r$ vertex classes) then $G$ must be isomorphic to $T_{r}(n)$.