Graph/Nachbarschaftsvergleich/Homomorphismus/Aufgabe/Lösung

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

   $\phi (x)\phi (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