Chromatisches Polynom/Genau k Farben/Fakt/Beweis

Beweis

Wir betrachten zulässige Färbungen von ${}G$ mit der Farbenmenge ${}\{1,\ldots ,k\}$. Die in Frage stehende Menge der zulässigen Färbungen mit genau ${}k$ Farben sind dabei die surjektiven Abbildungen. Zu ${}\ell \in \{1,\ldots ,k\}$ sei ${}F_{\ell }$ die Menge der zulässigen Färbungen in ${}\{1,\ldots ,k\}$, die ${}\ell$ nicht treffen. Zu einer Teilmenge ${}J\subseteq \{1,\ldots ,k\}$ ist ${}\bigcap _{\ell \in J}F_{\ell }$ die Menge der zulässigen Färbungen, die nur Farben aus ${}\{1,\ldots ,k\}\setminus J$ verwenden. Mit der Siebformel ist

${}{\#\left(\bigcup _{\ell =1}^{k}F_{\ell }\right)}=\sum _{j=1}^{k}(-1)^{j+1}{\binom {k}{j}}P_{G}\left(k-j\right)\,,$

der Übergang zum Komplement ergibt die Behauptung.

Zur bewiesenen Aussage