Handshaking lemma

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.

[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.

For graphs that are allowed to contain loops connecting a vertex to itself, a loop should be counted as contributing two units to the degree of its endpoint for the purposes of the handshaking lemma.

[2] Then, the handshaking lemma states that, in every finite graph, there must be an even number of vertices for which

That is, the sum of the vertex degrees equals twice the number of edges.

[6] In directed graphs, another form of the degree-sum formula states that the sum of in-degrees of all vertices, and the sum of out-degrees, both equal the number of edges.

[7] A version of the degree sum formula also applies to finite families of sets or, equivalently, multigraphs: the sum of the degrees of the elements (where the degree equals the number of sets containing it) always equals the sum of the cardinalities of the sets.

[8] Both results also apply to any subgraph of the given graph and in particular to its connected components.

[9] Leonhard Euler first proved the handshaking lemma in his work on the Seven Bridges of Königsberg, asking for a walking tour of the city of Königsberg (now Kaliningrad) crossing each of its seven bridges once.

This can be translated into graph-theoretic terms as asking for an Euler path or Euler tour of a connected graph representing the city and its bridges: a walk through the graph that traverses each edge once, either ending at a different vertex than it starts in the case of an Euler path or returning to its starting point in the case of an Euler tour.

Euler stated the fundamental results for this problem in terms of the number of odd vertices in the graph, which the handshaking lemma restricts to be an even number.

In the Christofides–Serdyukov algorithm for approximating the traveling salesperson problem, the geometric implications of the degree sum formula plays a vital role, allowing the algorithm to connect vertices in pairs in order to construct a graph on which an Euler tour forms an approximate TSP tour.

[10] Several combinatorial structures may be shown to be even in number by relating them to the odd vertices in an appropriate "exchange graph".

Thomason (1978) used a proof based on the handshaking lemma to extend this result to graphs in which all vertices have odd degree.

[12] The handshaking lemma (or degree sum formula) are also used in proofs of several other results in mathematics.

Since these two formulas count the same set of objects, they must have equal values.

The same proof can be interpreted as summing the entries of the incidence matrix of the graph in two ways, by rows to get the sum of degrees and by columns to get twice the number of edges.

[5] For graphs, the handshaking lemma follows as a corollary of the degree sum formula.

[5] Alternatively, it is possible to use mathematical induction to prove the degree sum formula,[2] or to prove directly that the number of odd-degree vertices is even, by removing one edge at a time from a given graph and using a case analysis on the degrees of its endpoints to determine the effect of this removal on the parity of the number of odd-degree vertices.

It follows from the same double counting argument that, in each subset, the sum of degrees equals the number of edges in the graph.

[22] The handshaking lemma does not apply in its usual form to infinite graphs, even when they have only a finite number of odd-degree vertices.

For instance, an infinite path graph with one endpoint has only a single odd-degree vertex rather than having an even number of such vertices.

It is also possible to find even-degree and odd-degree induced subgraphs with many vertices.

An induced subgraph of even degree can be found with at least half of the vertices, and an induced subgraph of odd degree (in a graph with no isolated vertices) can be found with

Papadimitriou (1994) investigated the computational complexity of questions such as this, or more generally of finding a second odd-degree vertex when one is given a single odd vertex in a large implicitly-defined graph.

He defined the complexity class PPA to encapsulate problems such as this one;[26] a closely related class defined on directed graphs, PPAD, has attracted significant attention in algorithmic game theory because computing a Nash equilibrium is computationally equivalent to the hardest problems in this class.

[27] Computational problems proven to be complete for the complexity class PPA include computational tasks related to Sperner's lemma[28] and to fair subdivision of resources according to the Hobby–Rice theorem.