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)$$


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.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.