Chromatisches Polynom/Konstruktionen/Fakt/Beweis

Beweis

(1). Sei ${}e=\{u,v\}$. Wir zeigen

${}P_{G\setminus \{e\}}=P_{G}+P_{G/e}\,,$

indem wir die zulässigen Färbungen analysieren. Eine zulässige Färbung von ${}G$ ist eine zulässige Färbung ${}f$ von ${}G\setminus \{e\}$, bei der auch die Bedingung ${}f(u)\neq f(v)$ erfüllt ist. Somit müssen wir zeigen, dass die zulässigen Färbungen von ${}G\setminus \{e\}$ mit ${}f(u)=f(v)$ den zulässigen Färbungen von ${}G/e$ entsprechen. Über den surjektiven schwachen Graphhomomorphismus

$\varphi \colon G\longrightarrow G/e$

erhält man aus einer zulässigen Färbung ${}f$ von ${}G/e$ direkt eine (nichtzulässige) Färbung ${}f\circ \varphi$ von ${}G$ mit identischem Wert auf ${}u$ und ${}v$ und damit direkt eine zulässige Färbung auf ${}G\setminus \{e\}$ mit identischem Wert auf ${}u$ und ${}v$. Diese Gesamtzuordnung ist injektiv. Wenn umgekehrt eine zulässige Färbung

$g\colon G\setminus \{e\}\longrightarrow B$

mit ${}g(u)=g(v)$ gegeben ist, so kann man dies direkt als eine Färbung auf ${}G/e$ auffassen. Wenn ${}d$ eine Kante von ${}G/e$ ist, so liegt dieser Kante eine Kante ${}d'$ in ${}G$ zugrunde, und daher überträgt sich die Zulässigkeit.

(2). Eine zulässige Färbung auf ${}G_{1}\uplus G_{2}$ mit ${}k$ Farben besteht einfach aus einer zulässigen Färbung von ${}G_{1}$ und einer zulässigen Färbung von ${}G_{2}$, es gibt darüber hinaus keine weitere Bedingung, da es ja keine Kanten zwischen ${}G_{1}$ und ${}G_{2}$ gibt. Die Anzahl der zulässigen Gesamtfärbungen ist daher das Produkt der Anzahlen der einzelnen zulässigen Färbungen.

Zur bewiesenen Aussage