Handshake lemma

In graph theory , the handshake lemma says that in every finite simple graph the sum of the degrees of all nodes is exactly twice as large as the number of its edges .

Formally, this means: If a graph is used and describes the degree of the node (in the case of directed graphs, both the input and output degrees are counted), then applies ${\displaystyle G=(V,E)}$ ${\displaystyle d_{G}(v)}$ ${\displaystyle v\in V}$

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

It follows immediately that every graph has an even number of nodes of odd degree.

At regular graph of the formula is simplified. For a -regular graph we have ${\displaystyle k}$

${\displaystyle k\cdot |V|=2\cdot |E|.}$

The handshake lemma was demonstrated by Leonhard Euler in the context of the Königsberg bridge problem in 1736 .

The name of the handshake lemma comes from the example that the number of people at a party shaking hands with an odd number of guests is even.

literature

• Lutz Volkmann: Foundations of the graph theory . Springer, Vienna 1996, ISBN 3-211-82774-9 , p. 5, sentence 1.1

Web links

• Handshake lemma on PlanetMath (English)  ( Page no longer available , searching web archives )
• Lutz Volkmann: Graphs on all corners and edges (PDF; 3.7 MB) . Script 2006, p. 4, sentence 1.1