# Chromatic polynomial properties

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

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

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

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.