(i) Define the chromatic polynomial $p(G ; t)$ of the graph $G$, and establish the standard identity

$$p(G ; t)=p(G-e ; t)-p(G / e ; t),$$

where $e$ is an edge of $G$. Deduce 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_{j} \geq 0$ for $0 \leq j \leq n$.

(ii) Let $G$ and $p(G ; t)$ be as in Part (i). Show that if $G$ has $k$ components $G_{1}, \ldots, G_{k}$ then $p(G ; t)=\prod_{i=1}^{k} p\left(G_{i} ; t\right)$. Deduce that $a_{k}>0$ and $a_{j}=0$ for $0 \leq j<k$.

Show that if $G$ is a tree then $p(G ; t)=t(t-1)^{n-1}$. Must the converse hold? Justify your answer.

Show that if $p(G ; t)=p\left(T_{r}(n) ; t\right)$, where $T_{r}(n)$ is a Turán graph, then $G=T_{r}(n)$.