
## Section5.4Chromatic Polynomial continued

The proof follows from induction on $m\text{,}$ the number of edges, using deletion-contraction for the inductive step.

As a base case, we take $m=0\text{.}$ Then if $\bfG$ has $n$ vertices it must be the empty graph $E_n\text{.}$ We have seen that $P_{E_n}(k)=k^n\text{,}$ which indeed has the correct form needed for the theorem.

Now, for the inductive step, we assume that for any graph $H$ with $\ell\lt m$ edges and $n$ vertices, we have $P_{H}(k)=k^n-\ell k^{n-1}+\text{lower order terms}\text{.}$

Now let $\bfG$ be any graph with $m$ edges. We can assume $m\gt 0\text{,}$ as the case where $m=0$ is the base case; this means that $\bfG$ has at least one edge $e\text{.}$ We apply deletion-contraction to the edge $e\text{.}$

If we delete $e\text{,}$ the resulting graph $\bfG\setminus e$ still has $n$ vertices, but it now has $m-1$ edges. Since this is less than $m\text{,}$ we know by the inductive hypothesis that

\begin{equation*} P_{\bfG\setminus e}(k)=k^n-(m-1)k^{n-1}+\text{lower order terms} \end{equation*}

If we contract $e\text{,}$ the resulting graph $\bfG/e$ has $n-1$ vertices, and we don't know exactly how many edges it has (contracting it may create multiple edges that need to be deleted), but it has at most $m-1$ edges, and so by the inductive hypothesis we know that

\begin{equation*} P_{\bfG/e}(k)=k^{n-1}+\text{lower order terms} \end{equation*}

Thus, applying deletion-contraction we have:

\begin{align*} P_\bfG(k) \amp = P_{\bfG\setminus e}(k)-P_{\bfG/e}(k) \\ \amp = k^n-(m-1)k^{n-1}+\text{lower order terms} - \left(k^{n-1}+\text{lower order terms} \right)\\ \amp = k^n-mk^{n-1}+\text{lower order terms} \end{align*}

which is what we needed to show to finish the inductive step.