Handschlaglemma

aus Wikipedia, der freien Enzyklopädie
Wechseln zu: Navigation, Suche

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[Bearbeiten]

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

Weblinks[Bearbeiten]