In graph theory

Graph theory

In mathematics and computer science, graph theory is the study of graphs, mathematical structures used to model pairwise relations between objects from a certain collection. A "graph" in this context refers to a collection of vertices or 'nodes' and a collection of edges that connect pairs of...

, a branch of mathematics, the handshaking lemma is the statement that every finite undirected graph has an even number of vertices with odd degree

Degree (graph theory)

In graph theory, the degree of a vertex of a graph is the number of edges incident to the vertex, with loops counted twice. The degree of a vertex v is denoted \deg. The maximum degree of a graph G, denoted by Δ, and the minimum degree of a graph, denoted by δ, are the maximum and minimum degree...

. In more colloquial terms, in a party of people some of whom shake hands, an even number of people must have shaken an odd number of other people's hands.

The handshaking lemma is a consequence of the degree sum formula (also sometimes called the handshaking lemma),
for a graph with vertex set

Vertex (graph theory)

In graph theory, a vertex or node is the fundamental unit out of which graphs are formed: an undirected graph consists of a set of vertices and a set of edges , while a directed graph consists of a set of vertices and a set of arcs...

 V and edge set E. Both results were proven by in his famous paper on the Seven Bridges of Königsberg

Seven Bridges of Königsberg

The Seven Bridges of Königsberg is a historically notable problem in mathematics. Its negative resolution by Leonhard Euler in 1735 laid the foundations of graph theory and prefigured the idea of topology....

 that began the study of graph theory.

The vertices of odd degree in a graph are sometimes called odd nodes or odd vertices; in this terminology, the handshaking lemma can be restated as the statement that every graph has an even number of odd nodes.

Proof

Euler's proof of the degree sum formula uses the technique of double counting

Double counting (proof technique)

In combinatorics, double counting, also called counting in two ways, is a combinatorial proof technique for showing that two expressions are equal by demonstrating that they are two ways of counting the size of one set...

: he counts the number of incident pairs (v,e) where e is an edge and vertex v is one of its endpoints, in two different ways. Vertex v belongs to deg(v) pairs, where deg(v) (the degree

Degree (graph theory)

In graph theory, the degree of a vertex of a graph is the number of edges incident to the vertex, with loops counted twice. The degree of a vertex v is denoted \deg. The maximum degree of a graph G, denoted by Δ, and the minimum degree of a graph, denoted by δ, are the maximum and minimum degree...

 of v) is the number of edges incident to it. Therefore the number of incident pairs is the sum of the degrees. However, each edge in the graph belongs to exactly two incident pairs, one for each of its endpoints; therefore, the number of incident pairs is 2|E|. Since these two formulas count the same set of objects, they must have equal values.

In a sum of integers, the parity of the sum is not affected by the even terms in the sum; the overall sum is even when there is an even number of odd terms, and odd when there is an odd number of odd terms. Since one side of the degree sum formula is the even number 2|E|, the sum on the other side must have an even number of odd terms; that is, there must be an even number of odd-degree vertices.

Regular graphs

The degree sum formula implies that every r-regular graph with n vertices has rn/2 edges. In particular, if r is odd then the number of edges must be evenly divisible by r.

Infinite graphs

The handshaking lemma does not apply to infinite graphs, even when they have only a finite number of odd-degree vertices. For instance, an infinite path graph

Path graph

In the mathematical field of graph theory, a path graph or linear graph is a particularly simple example of a tree, namely a tree with two or more vertices that is not branched at all, that is, contains only vertices of degree 2 and 1...

 with one endpoint has only a single odd-degree vertex rather than having an even number of such vertices.

Exchange graphs

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

For instance, as C. A. B. Smith proved, in any cubic graph

Cubic graph

In the mathematical field of graph theory, a cubic graph is a graph in which all vertices have degree three. In other words a cubic graph is a 3-regular graph. Cubic graphs are also called trivalent graphs....

 G there must be an even number of Hamiltonian cycles through any fixed edge uv; used a proof based on the handshaking lemma to extend this result to graphs G in which all vertices have odd degree. Thomason defines an exchange graph H, the vertices of which are in one-to-one correspondence with the Hamiltonian paths beginning at u and continuing through v. Two such paths p₁ and p₂ are connected by an edge in H if one may obtain p₂ by adding a new edge to the end of p₁ and removing another edge from the middle of p₁; this is a symmetric relation

Symmetric relation

In mathematics, a binary relation R over a set X is symmetric if it holds for all a and b in X that if a is related to b then b is related to a.In mathematical notation, this is:...

, so H is an undirected graph. If path p ends at vertex w, then the vertex corresponding to p in H has degree equal to the number of ways that p may be extended by an edge that does not connect back to u; that is, the degree of this vertex in H is either deg(w) − 1 (an even number) if p does not form part of a Hamiltonian cycle through uv, or deg(w) − 2 (an odd number) if p is part of a Hamiltonian cycle through uv. Since H has an even number of odd vertices, G must have an even number of Hamiltonian cycles through uv.

Computational complexity

In connection with the exchange graph method for proving the existence of combinatorial structures, it is of interest to ask how efficiently these structures may be found. For instance, suppose one is given as input a Hamiltonian cycle in a cubic graph; it follows from Smith's theorem that there exists a second cycle. How quickly can this second cycle be found?
investigated the computational complexity

Computational Complexity

Computational Complexity may refer to:*Computational complexity theory*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

Complexity class

In computational complexity theory, a complexity class is a set of problems of related resource-based complexity. A typical complexity class has a definition of the form:...

 PPA

PPA (complexity)

PPA is a complexity class, standing for "Polynomial Parity Argument" . Introduced by Christos Papadimitriou in 1994 , PPA is a subclass of TFNP...

 to encapsulate problems such as this one; a closely related class defined on directed graphs, PPAD

PPAD (complexity)

PPAD is a complexity class introduced by Christos Papadimitriou in 1994. PPAD is a subclass of TFNP based on functions that can be shown to be total by a parity argument...

, has attracted significant attention in algorithmic game theory

Algorithmic game theory

Algorithmic game theory is an area in the intersection of game theory and algorithm design, whose objective is to design algorithms in strategic environments. Typically, in Algorithmic Game Theory problems, the input to a given algorithm is distributed among many players who have a personal...

 because computing a Nash equilibrium

Nash equilibrium

In game theory, Nash equilibrium is a solution concept of a game involving two or more players, in which each player is assumed to know the equilibrium strategies of the other players, and no player has anything to gain by changing only his own strategy unilaterally...

 is computationally equivalent to the hardest problems in this class.

Other applications

The handshaking lemma is also used in proofs of Sperner's lemma

Sperner's lemma

In mathematics, Sperner's lemma is a combinatorial analog of the Brouwer fixed point theorem, which follows from it. Sperner's lemma states that every Sperner coloring of a triangulation of an n-dimensional simplex contains a cell colored with a complete set of colors...

 and of the piecewise linear case of the mountain climbing problem

Mountain climbing problem

In mathematics, the mountain climbing problem is a problem of finding conditions two function forming profiles of a two-dimensional mountain must satisfy, so that two climbers can start on the bottom on the opposite sides of the mountain and coordinate their movements to reach to the top while...

.