Chromatisches Polynom/Genau k Farben/Fakt/Beweis

Aus Wikiversity
Beweis

Wir betrachten zulässige Färbungen von mit der Farbenmenge . Die in Frage stehende Menge der zulässigen Färbungen mit genau Farben sind dabei die surjektiven Abbildungen. Zu sei die Menge der zulässigen Färbungen in , die nicht treffen. Zu einer Teilmenge ist die Menge der zulässigen Färbungen, die nur Farben aus verwenden. Mit der Siebformel ist

der Übergang zum Komplement ergibt die Behauptung.