Handshaking lemma

In graph theory the Handschlaglemma that in each graph the sum of the degrees of all nodes as large as exactly twice the number of its edges.

Formally, this means that So is a graph ( directed graph with both the inputs and the output -grade counted ), then with the degree of a node:

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

For regular graphs, the formula simplifies. For a k- regular graph applies:

The name of the Handschlaglemmas comes from the example that the number of persons, is just at a party, give an odd number of guests the hand.