Chromatisches Polynom/Genau k Farben/Fakt

Es sei ${}G$ ein Graph und ${}P_{G}$ sein chromatisches Polynom.

Dann ist die Anzahl der zulässigen Färbungen von ${}G$ mit genau ${}k$ Farben gleich

$\sum _{j=0}^{k}(-1)^{j}{\binom {k}{j}}P_{G}\left(k-j\right).$

Zum Beweis, Alternativen Beweis erstellen