imported>Schojoha am 20. April 2023 um 18:25 Uhr

2023-04-20T18:25:39Z

Neue Seite

In der [[Graphentheorie]], einem der [[Teilgebiete der Mathematik]], besagt das '''Handschlaglemma''' ({{enS|Handshaking lemma}}), dass in jedem [[Endlicher Graph|endlichen]] [[Einfacher Graph|einfachen Graphen]] die Summe der [[Grad (Graphentheorie)|Grade]] aller [[Knoten (Graphentheorie)|Knoten]] genau das [[Doppelt]]e seiner [[Kantenzahl]] ausmacht.

Formal heißt das: Ist <math>G=(V,E)</math> ein einfacher Graph und bezeichnet <math>d_G(v)</math> den [[Grad (Graphentheorie)|Grad]] des Knotens <math>v \in V</math> (bei gerichteten Graphen werden sowohl die Ein- als auch die Ausgangs-Grade gezählt), so gilt
:<math>\sum_{v\in V} d_G(v) = 2\cdot |E|.</math><ref group="A">Diese Formel besitzt eine [[Satz_von_Mantel#Hintergrund|Verallgemeinerung auf Hypergraphen]].</ref>

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

Bei [[Regulärer Graph|regulären Graphen]] vereinfacht sich die Formel. Für einen <math>k</math>-regulären Graphen gilt

:<math>k\cdot |V| = 2\cdot |E|.</math>

Das Handschlaglemma wurde im Rahmen des [[Königsberger Brückenproblem]]s 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 ==
* {{Literatur
|Autor=[[Stasys Jukna]]
|Titel=Extremal Combinatorics
|Reihe=Texts in Theoretical Computer Science
|Auflage=2.
|Verlag=Springer Verlag
|Ort=Heidelberg / Dordrecht / London / New York
|Datum=2011
|ISBN=978-3-642-17363-9
|Online=[https://mathscinet.ams.org/mathscinet/search/publdoc.html?arg3=&co4=AND&co5=AND&co6=AND&co7=AND&dr=all&pg4=AUCN&pg5=TI&pg6=PC&pg7=ALLF&pg8=ET&review_format=html&s4=Jukna%2C%20Stasys&s5=&s6=&s7=&s8=All&sort=Newest&vfpref=html&yearRangeFirst=&yearRangeSecond=&yrop=eq&r=17&mx-pid=2865719 MR2865719]}}
* Lutz Volkmann: ''Fundamente der Graphentheorie''. Springer, Wien 1996, ISBN 3-211-82774-9, S. 5, Satz 1.1

== Weblinks ==
* [https://planetmath.org/handshakelemma Handschlag-Lemma] auf [[PlanetMath]] (englisch)
* Lutz Volkmann: ''[https://www.math2.rwth-aachen.de/files/gt/buch/graphen_an_allen_ecken_und_kanten.pdf Graphen an allen Ecken und Kanten] (PDF; 3,5 MB)''. Skript 2006, S. 4, Satz 1.1

== Anmerkungen ==
<references group="A" />

[[Kategorie:Satz (Graphentheorie)]]

Handschlaglemma - Versionsgeschichte

imported>Schojoha am 20. April 2023 um 18:25 Uhr