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\leq n$. Für ${}k\geq n$. ist die Zahl links nach Fakt die Anzahl der injektiven Abbildungen von ${}G$ nach ${}\{1,\ldots ,k\}$, und diese sind stets zulässig. (3). Eine zulässige Färbung mit (höchstens) ${}k\geq n+1$ Farben ist eine zulässige Färbung mit genau ${}\ell$ Farben für ein ${}\ell =0,1,\ldots ,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{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}}$

Zur bewiesenen Aussage