Ungerichteter Graph/Grad/Einführung/Textabschnitt

Definition

Zu einem Punkt ${}v\in V$ in einem Graphen nennt man die Anzahl der Kanten, die an ${}v$ anliegen, den Grad von ${}v$. Er wird mit ${}d(v)$ bezeichnet.

Es ist also ${}d(v)={\#\left(N(v)\right)}$.

Die folgende Aussage (bzw. das darauf folgende Korollar) heißt auch Handschlaglemma. Man überlege sich eine Handschlaginterpretation für diese Aussagen.

Lemma

Es sei ${}(V,E)$ ein Graph.

Dann gilt

${}\sum _{v\in V}d(v)=2\cdot {\#\left(E\right)}\,.$

Beweis

Das kann man beispielsweise durch Induktion über die Anzahl der Kanten bei gegebener Knotenmenge beweisen. Beim einem kantenlosen Graphen steht links und rechts beidseitig ${}0$. Wenn man zu einem Graphen eine Kante hinzutut, sagen wir die Kante, die die beiden Punkte ${}u$ und ${}v$ verbindet, so erhöht sich der Grad von ${}u$ und der Grad von ${}v$ jeweils um ${}1$ und die anderen Grade bleiben unverändert. Somit erhöhen sich beide Seiten um ${}2$.

$\Box$

Korollar

Es sei ${}(V,E)$ ein Graph.

Dann ist die Anzahl der Knoten, die einen ungeraden Grad besitzen, gerade.

Beweis

Es sei ${}V_{g}$ die Knoten mit einem geraden Grad und ${}V_{u}$ die Knoten mit einem ungeraden Grad. Nach Fakt gilt

${}\sum _{v\in V_{g}}d(v)+\sum _{v\in V_{u}}d(v)=2\cdot {\#\left(E\right)}\,,$

diese Zahl ist also gerade. Der linke Summand ist als Summe von geraden Zahlen ebenfalls gerade. Somit muss auch der rechte Summand gerade sein. Dies kann nur sein, wenn die Anzahl von ${}V_{u}$ gerade ist.

$\Box$

Definition

Ein Punkt ${}v\in V$ eines Graphen mit Grad ${}0$ heißt isoliert.

Definition

Ein Punkt ${}v\in V$ eines Graphen mit Grad ${}1$ heißt Blatt.

Definition

Zu einem Graphen nennt man

${}\delta (G)={\min {\left(d(v),v\in V\right)}}\,$

den Minimalgrad des Graphen.

Definition

Zu einem Graphen nennt man

${}\Delta (G)={\max {\left(d(v),v\in V\right)}}\,$

den Maximalgrad des Graphen.