Graphen: Das Handshaking-Lemma

Das Handshaking-Lemma besagt:

 Für alle Graphen gilt, dass die Summe der Knotengrade genau zweimal so groß ist wie die Anzahl der Kanten.

Dies liegt daran, dass eine Kante immer zwischen zwei Knoten verläuft, und somit in der Berechnung beider Knotengrade eingeht.

Aus dem Handshaking-Lemma folgt, dass die Summe der Knotengrade gerade ist, da die Summe der Knotengrade immer zweimal so groß ist wie die Anzahl der Kanten. Weiterhin gilt, dass die Summe der Knotengrade der Knoten mit geradem Knotengrad ebenfalls gerade ist – da insgesamt die Summe der Knotengrade gerade ist. Daraus folgt auch, dass die Summe der Knotengrade mit ungeradem Knotengrad gerade sein muss. Eine Summe aus ungerade Zahlen ist genau dann gerade, wenn die Anzahl der Summanden gerade ist -> Summe der Knoten mit ungeradem Grad muss gerade sein!