Graph/Nachbarschaftsvergleich/Homomorphismus/Aufgabe/Lösung
- Die Äquivalenz von (1) und (2) ist klar. Es sei (2) erfüllt und sei die angegebene Abbildung. Wenn
sind, so werden sie auf sich selbst abgebildet und daher bleiben Kanten erhalten. Sei
.
Es wird auf sich selbst und auf abgebildet. Wenn es eine Kante zwischen
und
gibt, dann nach (2) auch zwischen
und .
Es sei umgekehrt (3) erfüllt und sei
.
Dann ist
und ist eine Kante. Da ein Graphhomomorphismus vorliegt, folgt, dass auch
eine Kante ist, also auch .
- Wir argumentieren mit (1). Damit ist unmittelbar klar, dass diese Relation transitiv und reflexiv ist. Sie ist im Allgemeinen aber nicht antisymmetrisch. Betrachten wir den Graphen mit drei Punkten , wobei
und
Kanten seien und keine Kante. Dann ist
und und stehen in Relation zueinander, sie sind aber nicht gleich.