Ungerichteter Graph/Grad/Einführung/Textabschnitt


Definition  

Zu einem Punkt in einem Graphen nennt man die Anzahl der Kanten, die an anliegen, den Grad von . Er wird mit bezeichnet.

Es ist also .

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


Lemma  

Es sei ein Graph.

Dann gilt

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 . Wenn man zu einem Graphen eine Kante hinzutut, sagen wir die Kante, die die beiden Punkte und verbindet, so erhöht sich der Grad von und der Grad von jeweils um und die anderen Grade bleiben unverändert. Somit erhöhen sich beide Seiten um .



Korollar  

Es sei ein Graph.

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

Beweis  

Es sei die Knoten mit einem geraden Grad und die Knoten mit einem ungeraden Grad. Nach Fakt gilt

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 gerade ist.



Definition  

Ein Punkt eines Graphen mit Grad heißt isoliert.


Definition  

Ein Punkt eines Graphen mit Grad heißt Blatt.


Definition  

Zu einem Graphen nennt man

den Minimalgrad des Graphen.


Definition  

Zu einem Graphen nennt man

den Maximalgrad des Graphen.