Handschlaglemma

Erklärung

Ein Graph besteht aus Knoten und Kanten, die je zwei Knoten verbinden. Der Grad $\deg(v)$ eines Knotens ist die Anzahl der Kanten, die an ihm enden. Das Handschlaglemma sagt: Addiert man alle Grade, erhält man die doppelte Kantenzahl.

Begründung durch doppeltes Abzählen: Jede Kante hat zwei Enden und wird deshalb in der Gradsumme genau zweimal gezählt, einmal bei jedem Endknoten. Eine Schleife (Kante von $v$ zu sich selbst) trägt $2$ zum Grad von $v$ bei, damit bleibt die Formel richtig.

Wichtigste Folgerung: Die Anzahl der Knoten mit ungeradem Grad ist immer gerade. Sonst wäre die Gradsumme ungerade.

Der Name kommt von der Deutung als Party: Knoten sind Gäste, Kanten Händedrücke. Die Summe aller gegebenen Hände ist doppelt so groß wie die Zahl der Händedrücke.

Beispiele

Ein Graph mit fünf Knoten hat die Grade $3, 2, 2, 3, 2$. Die Summe ist $12 = 2 \cdot 6$, also hat er $6$ Kanten.

Unmöglicher Graph: Kann jeder von $5$ Gästen genau $3$ anderen die Hand geben? Die Gradsumme wäre $5 \cdot 3 = 15$, also ungerade. Das ist unmöglich.

Vollständiger Graph $K_n$: Jeder der $n$ Knoten ist mit allen anderen verbunden, hat also Grad $n - 1$. Daraus folgt

Bei $6$ Gästen, die sich alle die Hand geben, sind das $\frac{6 \cdot 5}{2} = 15$ Händedrücke.

Würfel als Graph: $8$ Ecken mit je Grad $3$ ergeben $\frac{8 \cdot 3}{2} = 12$ Kanten.

Typische Fehler

• Den Faktor 2 vergessen. Die Gradsumme ist nicht die Kantenzahl. Bei $K_6$ ist die Gradsumme $30$, es gibt aber $15$ Kanten.
• Schleifen einfach zählen. Eine Schleife erhöht den Grad um $2$, nicht um $1$.
• Auf gerichtete Graphen übertragen. Dort gilt stattdessen: Summe der Eingangsgrade gleich Summe der Ausgangsgrade gleich $|E|$.