Chromatisches Polynom/Erste Eigenschaften/Fakt/Beweis

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

${\displaystyle {}{\begin{aligned}\sum _{\ell =0}^{n}{\binom {k}{\ell }}Q(\ell )&=\sum _{\ell =0}^{n}{\binom {k}{\ell }}{\left(\sum _{j=0}^{\ell }(-1)^{j}{\binom {\ell }{j}}P_{G}\left(\ell -j\right)\right)}\\&=\sum _{\ell =0}^{n}{\binom {k}{\ell }}{\left(\sum _{j=0}^{\ell }(-1)^{\ell -j}{\binom {\ell }{j}}P_{G}\left(j\right)\right)}\\&=\sum _{j=0}^{n}{\left(\sum _{\ell =j}^{n}(-1)^{\ell -j}{\binom {k}{\ell }}{\binom {\ell }{j}}\right)}P_{G}\left(j\right).\end{aligned}}}$