Handschlaglemma

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

In der Graphentheorie besagt das Handschlaglemma, dass in jedem schlichten 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 | Quelltext bearbeiten]

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

Weblinks[Bearbeiten | Quelltext bearbeiten]