Misplaced Pages

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. The handshaking lemma is a consequence of the degree sum formula, also sometimes called the handshaking lemma, 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.

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.

Definitions and statement

An undirected graph consists of a system of vertices, and edges connecting unordered pairs of vertices. In any graph, the degree ${\displaystyle \deg(v)}$ of a vertex ${\displaystyle v}$ is defined as the number of edges that have ${\displaystyle v}$ as an endpoint. 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. Then, the handshaking lemma states that, in every finite graph, there must be an even number of vertices for which ${\displaystyle \deg(v)}$ is an odd number. The vertices of odd degree in a graph are sometimes called odd nodes (or odd vertices); in this terminology, the handshaking lemma can be rephrased as the statement that every graph has an even number of odd nodes.

The degree sum formula states that $${\displaystyle \sum _{v\in V}\deg v=2|E|,}$$ where ${\displaystyle V}$ is the set of nodes (or vertices) in the graph and ${\displaystyle E}$ is the set of edges in the graph. That is, the sum of the vertex degrees equals twice the number of edges. 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. Here, the in-degree is the number of incoming edges, and the out-degree is the number of outgoing edges. 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.

Both results also apply to any subgraph of the given graph and in particular to its connected components. A consequence is that, for any odd vertex, there must exist a path connecting it to another odd vertex.

Applications

Euler paths and tours

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. If this number is zero, an Euler tour exists, and if it is two, an Euler path exists. Otherwise, the problem cannot be solved. In the case of the Seven Bridges of Königsberg, the graph representing the problem has four odd vertices, and has neither an Euler path nor an Euler tour. It was therefore impossible to tour all seven bridges in Königsberg without repeating a bridge.

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.

Combinatorial enumeration

Several combinatorial structures 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 ${\displaystyle G}$ there must be an even number of Hamiltonian cycles through any fixed edge ${\displaystyle uv}$; these are cycles that pass through each vertex exactly once. Thomason (1978) used a proof based on the handshaking lemma to extend this result to graphs in which all vertices have odd degree. Thomason defines an exchange graph ${\displaystyle H}$, the vertices of which are in one-to-one correspondence with the Hamiltonian paths in ${\displaystyle G}$ beginning at ${\displaystyle u}$ and continuing through edge ${\displaystyle uv}$. Two such paths ${\displaystyle p_{1}}$ and ${\displaystyle p_{2}}$ are defined as being connected by an edge in ${\displaystyle H}$ if one may obtain ${\displaystyle p_{2}}$ by adding a new edge to the end of ${\displaystyle p_{1}}$ and removing another edge from the middle of ${\displaystyle p_{1}}$. This operation is reversible, forming a symmetric relation, so ${\displaystyle H}$ is an undirected graph. If path ${\displaystyle p}$ ends at vertex ${\displaystyle w}$, then the vertex corresponding to ${\displaystyle p}$ in ${\displaystyle H}$ has degree equal to the number of ways that ${\displaystyle p}$ may be extended by an edge that does not connect back to ${\displaystyle u}$; that is, the degree of this vertex in ${\displaystyle H}$ is either ${\displaystyle \deg(w)-1}$ (an even number) if ${\displaystyle p}$ does not form part of a Hamiltonian cycle through ${\displaystyle uv}$, or ${\displaystyle \deg(w)-2}$ (an odd number) if ${\displaystyle p}$ is part of a Hamiltonian cycle through ${\displaystyle uv}$. Since ${\displaystyle H}$ has an even number of odd vertices, ${\displaystyle G}$ must have an even number of Hamiltonian cycles through ${\displaystyle uv}$.

Other applications

The handshaking lemma (or degree sum formula) are also used in proofs of several other results in mathematics. These include the following:

• Sperner's lemma states that, if a big triangle is subdivided into smaller triangles meeting edge-to-edge, and the vertices are labeled with three colors so that only two of the colors are used along each edge of the big triangle, then at least one of the smaller triangles has vertices of all three colors; it has applications in fixed-point theorems, root-finding algorithms, and fair division. One proof of this lemma forms an exchange graph whose vertices are the triangles (both small and large) and whose edges connect pairs of triangles that share two vertices of some particular two colors. The big triangle necessarily has odd degree in this exchange graph, as does a small triangle with all three colors, but not the other small triangles. By the handshaking lemma, there must be an odd number of small triangles with all three colors, and therefore at least one such triangle must exist.

• The mountain climbing problem states that, for sufficiently well-behaved functions on a unit interval, with equal values at the ends of the interval, it is possible to coordinate the motion of two points, starting from opposite ends of the interval, so that they meet somewhere in the middle while remaining at points of equal value throughout the motion. One proof of this involves approximating the function by a piecewise linear function with the same extreme points, parameterizing the position of the two moving points by the coordinates of a single point in the unit square, and showing that the available positions for the two points form a finite graph, embedded in this square, with only the starting position and its reversal as odd vertices. By the handshaking lemma, these two positions belong to the same connected component of the graph, and a path from one to the other necessarily passes through the desired meeting point.
• The reconstruction conjecture concerns the problem of uniquely determining the structure of a graph from the multiset of subgraphs formed by removing a single vertex from it. Given this information, the degree-sum formula can be used to recover the number of edges in the given graph and the degrees of each vertex. From this, it is possible to determine whether the given graph is a regular graph, and if so to determine it uniquely from any vertex-deleted subgraph by adding a new neighbor for all the subgraph vertices of too-low degree. Therefore, all regular graphs can be reconstructed.
• The game of Hex is played by two players, who place pieces of their color on a tiling of a parallelogram-shaped board by hexagons until one player has a connected path of adjacent pieces from one side of the board to the other. It can never end in a draw: by the time the board has been completely filled with pieces, one of the players will have formed a winning path. One proof of this forms a graph from a filled game board, with vertices at the corners of the hexagons, and with edges on sides of hexagons that separate the two players' colors. This graph has four odd vertices at the corners of the board, and even vertices elsewhere, so it must contain a path connecting two corners, which necessarily has a winning path for one player on one of its sides.

Proof

Euler's proof of the degree sum formula uses the technique of double counting: he counts the number of incident pairs ${\displaystyle (v,e)}$ where ${\displaystyle e}$ is an edge and vertex ${\displaystyle v}$ is one of its endpoints, in two different ways. Vertex ${\displaystyle v}$ belongs to ${\displaystyle \deg(v)}$ pairs, where ${\displaystyle \deg(v)}$ (the degree of ${\displaystyle 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 ${\displaystyle 2|E|}$. 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.

For graphs, the handshaking lemma follows as a corollary of the degree sum formula. 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 ${\displaystyle 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.

Alternatively, it is possible to use mathematical induction to prove the degree sum formula, 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.

In special classes of graphs

Regular graphs

The degree sum formula implies that every ${\displaystyle r}$-regular graph with ${\displaystyle n}$ vertices has ${\displaystyle nr/2}$ edges. Because the number of edges must be an integer, it follows that when ${\displaystyle r}$ is odd the number of vertices must be even. Additionally, for odd values of ${\displaystyle r}$, the number of edges must be divisible by ${\displaystyle r}$.

Bipartite and biregular graphs

A bipartite graph has its vertices split into two subsets, with each edge having one endpoint in each subset. It follows from the same double counting argument that, in each subset, the sum of degrees equals the number of edges in the graph. In particular, both subsets have equal degree sums. For biregular graphs, with a partition of the vertices into subsets ${\displaystyle V_{1}}$ and ${\displaystyle V_{2}}$ with every vertex in a subset ${\displaystyle V_{i}}$ having degree ${\displaystyle r_{i}}$, it must be the case that ${\displaystyle |V_{1}|r_{1}=|V_{2}|r_{2}}$; both equal the number of edges.

Infinite graphs

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. However, it is possible to formulate a version of the handshaking lemma using the concept of an end, an equivalence class of semi-infinite paths ("rays") considering two rays as equivalent when there exists a third ray that uses infinitely many vertices from each of them. The degree of an end is the maximum number of edge-disjoint rays that it contains, and an end is odd if its degree is finite and odd. More generally, it is possible to define an end as being odd or even, regardless of whether it has infinite degree, in graphs for which all vertices have finite degree. Then, in such graphs, the number of odd vertices and odd ends, added together, is either even or infinite.

Subgraphs

By a theorem of Gallai the vertices of any graph can be partitioned as ${\displaystyle V=V_{e}\cup V_{o}}$ where in the two resulting induced subgraphs, ${\displaystyle G}$ has all degrees even and ${\displaystyle G}$ has all degrees odd. Here, ${\displaystyle |V_{o}|}$ must be even by the handshaking lemma. 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 ${\displaystyle |V_{o}|/|V|>1/10000}$.

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? 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; 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.

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

Notes

1. ^ Hein, James L. (2015), "Example 3: The Handshaking Problem", Discrete Structures, Logic, and Computability, Jones & Bartlett Publishers, p. 703, ISBN 9781284070408
2. ^ Gunderson, David S. (2014), Handbook of Mathematical Induction: Theory and Applications, CRC Press, p. 240, ISBN 9781420093650
3. ^ Euler, L. (1736), "Solutio problematis ad geometriam situs pertinentis", Commentarii Academiae Scientiarum Imperialis Petropolitanae, 8: 128–140. Reprinted and translated in Biggs, N. L.; Lloyd, E. K.; Wilson, R. J. (1976), Graph Theory 1736–1936, Oxford University Press
4. ^ Higgins, Peter M. (1998), Mathematics for the Curious, Oxford University Press, p. 201, ISBN 9780192880727
5. ^ Biggs, Norman L. (2002), "15.3: Degree", Discrete Mathematics, Oxford University Press, pp. 181–182, ISBN 9780198507178
6. West, Douglas B. (1996), "1.3.3. Theorem. (Degree-Sum Formula)", Introduction to Graph Theory (2nd ed.), Prentice Hall, p. 26, ISBN 9780132278287
7. Loehr, Nicholas (2011), "3.31. Theorem: Degree-Sum Formula for Digraphs", Bijective Combinatorics, CRC Press, p. 106, ISBN 9781439848869
8. ^ Jukna, Stasys (2011), "Proposition 1.7", Extremal Combinatorics, Texts in Theoretical Computer Science. An EATCS Series, Springer, p. 9, doi:10.1007/978-3-642-17364-6, ISBN 978-3-642-17363-9
9. Ray, Santanu Saha (2012), "Theorem 2.2", Graph Theory with Algorithms and its Applications in Applied Science and Technology, Springer, p. 16, ISBN 9788132207504
10. Christofides, Nicos (1976), Worst-case analysis of a new heuristic for the travelling salesman problem (PDF), Report 388, Graduate School of Industrial Administration, CMU, archived (PDF) from the original on 2019-07-21. The handshaking lemma is cited at the top of page 2.
11. Cameron, Kathie; Edmonds, Jack (1999), "Some graphic uses of an even number of odd nodes", Annales de l'Institut Fourier, 49 (3): 815–827, doi:10.5802/aif.1694, MR 1703426
12. Thomason, A. G. (1978), "Hamiltonian cycles and uniquely edge colourable graphs", Advances in Graph Theory (Cambridge Combinatorial Conf., Trinity College, Cambridge, 1977), Annals of Discrete Mathematics, vol. 3, pp. 259–268, doi:10.1016/S0167-5060(08)70511-9, ISBN 978-0-7204-0843-0, MR 0499124
13. Aigner, Martin; Ziegler, Günter M. (2018), "Section 28.6: Sperner's Lemma", Proofs from THE BOOK (6th ed.), Berlin: Springer, pp. 203–205, doi:10.1007/978-3-662-57265-8, ISBN 978-3-662-57264-1, MR 3823190
14. Goodman, Jacob E.; Pach, János; Yap, Chee-K. (1989), "Mountain climbing, ladder moving, and the ring-width of a polygon" (PDF), The American Mathematical Monthly, 96 (6): 494–510, doi:10.2307/2323971, JSTOR 2323971, MR 0999412
15. Lauri, Josef; Scapellato, Raffaele (2016), Topics in Graph Automorphisms and Reconstruction, London Mathematical Society Lecture Note Series, vol. 432 (2nd ed.), Cambridge University Press, pp. 105–106, doi:10.1017/CBO9781316669846, ISBN 978-1-316-61044-2, MR 3496604
16. Gale, David (1979), "The game of Hex and the Brouwer fixed-point theorem", The American Mathematical Monthly, 86 (10): 818–827, doi:10.1080/00029890.1979.11994922, JSTOR 2320146, MR 0551501
17. Neto, Antonio Caminha Muniz (2018), An Excursion through Elementary Mathematics, Volume III: Discrete Mathematics and Polynomial Algebra, Problem Books in Mathematics, Springer, pp. 132, 562, ISBN 9783319779775
18. Aldous, Joan M.; Wilson, Robin J. (2000), "Theorem 2.2", Graphs and Applications: an Introductory Approach, Undergraduate Mathematics Series, The Open University, Springer-Verlag, p. 44, ISBN 978-1-85233-259-4
19. Wallis, W. D. (2011), "Section 7.1, Introduction to Graphs, Corollary 1", A Beginner's Guide to Discrete Mathematics (2nd ed.), Springer, p. 219, ISBN 9780817682866
20. Clark, John; Holton, Derek Allan (1995), "Problem 1.4.6", A First Look at Graph Theory, Allied Publishers, p. 16, ISBN 9788170234630
21. Lovász, László (2014), Combinatorial Problems and Exercises (2nd ed.), Elsevier, p. 281, ISBN 9780080933092
22. Pisanski, Tomaž; Servatius, Brigitte (2013), "2.3.4: Semiregular Bipartite Graphs", Configurations from a Graphical Viewpoint, Birkhäuser Advanced Texts: Basler Lehrbücher, New York: Birkhäuser/Springer, p. 35, doi:10.1007/978-0-8176-8364-1, ISBN 978-0-8176-8363-4, MR 2978043
23. Bruhn, Henning; Stein, Maya (2007), "On end degrees and infinite cycles in locally finite graphs", Combinatorica, 27 (3): 269–291, doi:10.1007/s00493-007-2149-0, MR 2345811, S2CID 8367713; see Proposition 15, p. 284
24. Ferber, Asaf; Krivelevich, Michael (2022), "Every graph contains a linearly sized induced subgraph with all degrees odd", Advances in Mathematics, 406 108534, arXiv:2009.05495, doi:10.1016/j.aim.2022.108534, MR 4448268
25. Honner, Patrick (March 24, 2022), "What a Math Party Game Tells Us About Graph Theory", Quanta, retrieved 2022-03-27
26. Papadimitriou, Christos H. (1994), "On the complexity of the parity argument and other inefficient proofs of existence", Journal of Computer and System Sciences, 48 (3): 498–532, doi:10.1016/S0022-0000(05)80063-7, MR 1279412
27. Chen, Xi; Deng, Xiaotie (2006), "Settling the complexity of two-player Nash equilibrium", Proc. 47th Symp. Foundations of Computer Science, pp. 261–271, doi:10.1109/FOCS.2006.69, ISBN 0-7695-2720-5, S2CID 14102058, ECCC TR05-140
28. Grigni, Michelangelo (2001), "A Sperner lemma complete for PPA", Information Processing Letters, 77 (5–6): 255–259, doi:10.1016/S0020-0190(00)00152-6, MR 1818525
29. Filos-Ratsikas, Aris; Goldberg, Paul W. (2018), "Consensus halving is PPA-complete", in Diakonikolas, Ilias; Kempe, David; Henzinger, Monika (eds.), Proceedings of the 50th Annual ACM SIGACT Symposium on Theory of Computing, STOC 2018, Los Angeles, CA, USA, June 25-29, 2018, pp. 51–64, arXiv:1711.04503, doi:10.1145/3188745.3188880, ISBN 978-1-4503-5559-9, S2CID 8111195

• Lemmas in graph theory