Chromatic polynomial properties

The proof works by strong induction on $m=|E(G)|$. We also prove that the coefficient of $k^{n-1}$ is $m$ the number of edges.

Base case : $m=0$. Then $G$ is $n$ isolated vertices. And clearly $P_G(k) = k^n$. Satisfying all results\

Induction : Suppose the hypothesis are true for all graphs with at most $m$ edges. Let $G$ be a graph on $m+1$ edegs, $n$ vertices, $q$ components, and let $e \in E(G)$. Then

• $G-e$ has $m$ edges, $n$ vertices, $q$ or $q+1$ components
• $G/e$ has at most $m$ edges, with $n-1$ vertices, and $q$ components.

Using the induction hypothesis : \begin{align} P_{G-e}(k) = k^n - m &k^{n-1} + \ldots - \ldots \pm bk^q \\ P_{G/e}(k) = &k^{n-1} - \ldots + \ldots \mp ck^q \end{align} With $b\geq 0$ and $c>0$. Therefore $$ P_G(k) = k^n - (m+1) k^n + \ldots - \ldots + \ldots \pm (b+c)k^q$$ With $b+c >0$. Provind that $P_G(k)$ is monic, with alternating signs, with second coefficient $m+1$ its number of edges, and smallest coefficient the number $q$ of components.