Ungerichteter Graph/Schwacher Homomorphismus/Faktorisierung/Fakt/Beweis

Beweis

Wir definieren die Äquivalenzrelation ${}\sim$ auf ${}V$ durch ${}u\sim v$, wenn ${}\varphi (u)=\varphi (v)$. Es gibt dann nach Fakt eine Abbildung

$\psi \colon V/\sim \longrightarrow W,$

wodurch ${}\varphi$ faktorisiert. Dabei ist ${}\psi$ injektiv und ebenfalls nach der Definition der Kanten auf ${}G/\sim$ ein Graphhomomorphismus. Der Bildgraph zu ${}\psi$ (der auch der Bildgraph von ${}\varphi$ ist), ist ein Untergraph ${}(U,K)$ von ${}H$, der zu ${}G/\sim$ isomorph ist. Wenn man ${}(U,K)$ durch die Kanten aus ${}F$ auffüllt, die zwischen Punkten aus ${}U$ verlaufen, so erhält man einen knotenpunktgleichen vollen Untergraphen von ${}H$.

Zur bewiesenen Aussage