Graphhomomorphismus/Gradeigenschaft/Aufgabe/Lösung

Es seien ${}v_{1},\ldots ,v_{n}$ die an ${}P$ anliegenden Punkte, also ${}d(P)=n$ . Diese werden auf verschiedene Punkte ${}\varphi (v_{i})$ abgebildet und es ist stets ${}\varphi (P)\varphi (v_{i})$ eine Kante von ${}H$ . Also liegen an ${}\varphi (P)$ zumindest ${}n$ Kanten an.
Ohne die Voraussetzung injektiv ist die Aussage aus (1) nicht richtig. Betrachten wir den linearen Graphen ${}1,2,3$ , also mit den zwei Kanten ${}\{1,2\}$ und ${}\{2,3\}$ , und die Abbildung auf den linearen Graphen ${}a,b$ , also mit der Kante ${}\{a,b\}$ , der ${}1$ und ${}3$ auf ${}a$ und ${}2$ auf ${}b$ abbildet. Da Kanten auf Kanten gehen, liegt ein Graphhomomorphismus vor. Der Grad von ${}2$ ist aber gleich ${}2$ , während der Grad von ${}b$ gleich ${}1$ ist.