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