Chromatisches Polynom/Erste Eigenschaften/Fakt/Beweis

Beweis

(1) ist klar. (2). Die rechte Abschätzung ist klar, da rechts die Anzahl der Färbungen mit $k$ Farben überhaupt ohne Zulässigkeitsbedingung steht. Die linke Seite ist klar für  $k\le n$.  Für  $k\ge n$  ist die Zahl links nach Fakt die Anzahl der injektiven Abbildungen von $G$ nach $\{1,\dots ,k\}$, und diese sind stets zulässig. (3). Eine zulässige Färbung mit (höchstens)  $k\ge n+1$  Farben ist eine zulässige Färbung mit genau $\ell$ Farben für ein  $\ell =0,1,\dots ,n$.  Es sei $Q(\ell )$ die Anzahl der zulässigen Färbungen mit genau $\ell$ Farben. Dann ist die Anzahl der zulässigen Färbungen mit $k$ Farben unter Verwendung von Fakt gleich

$\begin{array}{cc}\sum _{\ell =0}^n(\genfrac{}{}{0ex}{}{k}{\ell })Q(\ell )& =\sum _{\ell =0}^n(\genfrac{}{}{0ex}{}{k}{\ell })(\sum _{j=0}^{\ell }(-1{)}^j(\genfrac{}{}{0ex}{}{\ell }{j})P_G(\ell -j))\\ & =\sum _{\ell =0}^n(\genfrac{}{}{0ex}{}{k}{\ell })(\sum _{j=0}^{\ell }(-1{)}^{\ell -j}(\genfrac{}{}{0ex}{}{\ell }{j})P_G\left(j\right))\\ & =\sum _{j=0}^n(\sum _{\ell =j}^n(-1{)}^{\ell -j}(\genfrac{}{}{0ex}{}{k}{\ell })(\genfrac{}{}{0ex}{}{\ell }{j}))P_G\left(j\right).\end{array}$

Zur bewiesenen Aussage