Handschlaglemma

In der Graphentheorie besagt das Handschlaglemma, dass in jedem Graph die Summe der Grade aller Knoten genau doppelt so groß ist wie die Anzahl seiner Kanten.

Formal heißt das: Ist G = (V,E) ein Graph (bei gerichteten Graphen werden sowohl die Ein- als auch die Ausgangs-Grade gezählt), so gilt also mit dem Grad d(v) eines Knotens v aus V:

$\sum_{v\in V} d(v) = 2\cdot |E|$

Daraus folgt sofort, dass jeder Graph eine gerade Anzahl von Knoten ungeraden Grades hat.

Bei regulären Graphen vereinfacht sich die Formel. Für einen k-regulären Graphen gilt:

$k\cdot |V| = 2\cdot |E|$

Der Name des Handschlaglemmas kommt von dem Beispiel, dass die Anzahl der Personen auf einer Party, die einer ungeraden Zahl von Gästen die Hand geben, gerade ist.

Literatur

• Lutz Volkmann: Fundamente der Graphentheorie, Springer (Wien) 1996, ISBN 3-211-82774-9, S. 5, Satz 1.1

Weblinks

• Handschlag-Lemma auf PlanetMath (engl.)
• Lutz Volkmann: Graphen an allen Ecken und Kanten. Skript 2006, S. 4, Satz 1.1