Handshaking lemma

In this graph, an even number of vertices (the four vertices numbered 2, 4, 5, and 6) have odd degrees. The sum of degrees of all six vertices is 2 + 3 + 2 + 3 + 3 + 1 = 14, twice the number of edges.

In graph theory, the handshaking lemma is the statement that, in every finite undirected graph, the number of vertices that touch an odd number of edges is even. For example, if there is a party of people who shake hands, the number of people who shake an odd number of other people's hands is even.[1] The handshaking lemma is a consequence of the degree sum formula, also sometimes called the handshaking lemma,[2] according to which the sum of the degrees (the numbers of times each vertex is touched) equals twice the number of edges in the graph. Both results were proven by Leonhard Euler (1736) in his famous paper on the Seven Bridges of Königsberg that began the study of graph theory.[3]

Beyond the Seven Bridges of Königsberg Problem, which subsequently formalized Eulerian Tours, other applications of the degree sum formula include proofs of certain combinatorial structures. For example, in the proofs of Sperner's lemma and the mountain climbing problem the geometric properties of the formula commonly arise. The complexity class PPA encapsulates the difficulty of finding a second odd vertex, given one such vertex in a large implicitly-defined graph.

  1. ^ Cite error: The named reference hein was invoked but never defined (see the help page).
  2. ^ Cite error: The named reference gunderson was invoked but never defined (see the help page).
  3. ^ Cite error: The named reference euler was invoked but never defined (see the help page).