Ungerichteter Graph/Grad/Einführung/Textabschnitt


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.


Es sei ein Graph.

Dann gilt

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 .



Es sei ein Graph.

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

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.



Ein Punkt eines Graphen mit Grad heißt isoliert.


Ein Punkt eines Graphen mit Grad heißt Blatt.


Zu einem Graphen nennt man

den Minimalgrad des Graphen.


Zu einem Graphen nennt man

den Maximalgrad des Graphen.