Handschlaglemma

In der Graphentheorie, einem der Teilgebiete der Mathematik, besagt das Handschlaglemma (englisch Handshaking lemma), dass in jedem endlichen einfachen Graphen die Summe der Grade aller Knoten genau das Doppelte seiner Kantenzahl ausmacht.

Formal heißt das: Ist $G=(V,E)$ ein einfacher Graph und bezeichnet $d_{G}(v)$ den Grad des Knotens $v\in V$ (bei gerichteten Graphen werden sowohl die Ein- als auch die Ausgangs-Grade gezählt), so gilt

\sum _{v\in V}d_{G}(v)=2\cdot |E|.

^{[A 1]}

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

Das Handschlaglemma wurde im Rahmen des Königsberger Brückenproblems 1736 von Leonhard Euler bewiesen.

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

Stasys Jukna: Extremal Combinatorics (= Texts in Theoretical Computer Science). 2. Auflage. Springer Verlag, Heidelberg / Dordrecht / London / New York 2011, ISBN 978-3-642-17363-9 (MR2865719).
Lutz Volkmann: Fundamente der Graphentheorie. Springer, Wien 1996, ISBN 3-211-82774-9, S. 5, Satz 1.1

Weblinks Bearbeiten

Handschlag-Lemma auf PlanetMath (englisch)
Lutz Volkmann: Graphen an allen Ecken und Kanten (PDF; 3,5 MB). Skript 2006, S. 4, Satz 1.1

Anmerkungen Bearbeiten

↑ Diese Formel besitzt eine Verallgemeinerung auf Hypergraphen.

[1] Diese Formel besitzt eine Verallgemeinerung auf Hypergraphen.

[A 1]