Graph/Nachbarschaftsvergleich/Homomorphismus/Aufgabe/Lösung

1. Die Äquivalenz von (1) und (2) ist klar. Es sei (2) erfüllt und sei ${}\varphi$ die angegebene Abbildung. Wenn ${}u,v\neq x$ sind, so werden sie auf sich selbst abgebildet und daher bleiben Kanten erhalten. Sei ${}u\neq x$. Es wird ${}u$ auf sich selbst und ${}x$ auf ${}y$ abgebildet. Wenn es eine Kante zwischen ${}u$ und ${}x$ gibt, dann nach (2) auch zwischen ${}u$ und ${}y$. Es sei umgekehrt (3) erfüllt und sei ${}z\in N(x)$. Dann ist ${}z\neq x$ und ${}xz$ ist eine Kante. Da ein Graphhomomorphismus vorliegt, folgt, dass auch

   ${}\varphi (x)\varphi (z)=yz\,$

   eine Kante ist, also auch ${}z\in N(y)$.

2. 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 ${}x,y,z$, wobei ${}xz$ und ${}yz$ Kanten seien und ${}xy$ keine Kante. Dann ist

   ${}N(x)=N(y)=\{z\}\,$

   und ${}x$ und ${}y$ stehen in Relation zueinander, sie sind aber nicht gleich.

Zur gelösten Aufgabe