Zum Inhalt springen

Ungerichteter Graph/Schwacher Homomorphismus/Faktorisierung/Fakt/Beweis

Aus Wikiversity
Beweis

Wir definieren die Äquivalenzrelation auf durch , wenn . Es gibt dann nach Fakt eine Abbildung

wodurch faktorisiert. Dabei ist injektiv und ebenfalls nach der Definition der Kanten auf ein Graphhomomorphismus. Der Bildgraph zu (der auch der Bildgraph von ist), ist ein Untergraph von , der zu isomorph ist. Wenn man durch die Kanten aus auffüllt, die zwischen Punkten aus verlaufen, so erhält man einen knotenpunktgleichen vollen Untergraphen von .