Graphhomomorphismus/Gradeigenschaft/Aufgabe/Lösung

1. 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.
2. 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.

Zur gelösten Aufgabe