Chromatic polynomial properties

Question

I have some properties which I do not understand how to form a proof for. Most of them are by induction, which is not my strong point Any help would be fantastic.

Looking at the chromatic polynomial $$P_G(k)=P_{G-e}(k) - P_{G/e}(k)$$

Properties

1.If G has n vertices then $ P_g(k)$ has degree n and the coefficient of $k^n $ is 1

2. The signs of $P_g(k) $ alternate

3. If G has q components the smalles non-zero term of $P_g(k)$ is the term in $k^q$

Answer 1

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.