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.