Handshaking lemma

Last updated

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. 6n-graf.svg
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, a branch of mathematics, 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 LeonhardEuler  ( 1736 ) in his famous paper on the Seven Bridges of Königsberg that began the study of graph theory. [3]

Contents

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 of a vertex is defined as the number of edges that have 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. [2] Then, the handshaking lemma states that, in every finite graph, there must be an even number of vertices for which is an odd number. [1] The vertices of odd degree in a graph are sometimes called odd nodes (or odd vertices); [4] in this terminology, the handshaking lemma can be rephrased as the statement that every graph has an even number of odd nodes. [4] [5]

The degree sum formula states that

where is the set of nodes (or vertices) in the graph and is the set of edges in the graph. 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. Here, the in-degree is the number of incoming edges, and the out-degree is the number of outgoing 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. A consequence is that, for any odd vertex, there must exist a path connecting it to another odd vertex. [9]

Applications

Euler paths and tours

7 bridges.svg
Schematic view of Königsberg's seven bridges
Konigsberg graph.svg
Graph with vertices for each land mass and an edge for each bridge

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. [3] 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. [10]

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". [11]

For instance, as C. A. B. Smith proved, in any cubic graph there must be an even number of Hamiltonian cycles through any fixed edge ; 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 , the vertices of which are in one-to-one correspondence with the Hamiltonian paths in beginning at and continuing through edge . Two such paths and are defined as being connected by an edge in if one may obtain by adding a new edge to the end of and removing another edge from the middle of . This operation is reversible, forming a symmetric relation, so is an undirected graph. If path ends at vertex , then the vertex corresponding to in has degree equal to the number of ways that may be extended by an edge that does not connect back to ; that is, the degree of this vertex in is either (an even number) if does not form part of a Hamiltonian cycle through , or (an odd number) if is part of a Hamiltonian cycle through . Since has an even number of odd vertices, must have an even number of Hamiltonian cycles through . [12]

Other applications

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

A Sperner coloring of a triangulated triangle, shaded to highlight the three small triangles that have all three vertex colors Sperner2d.svg
A Sperner coloring of a triangulated triangle, shaded to highlight the three small triangles that have all three vertex colors
The mountain climbing problem Mountain climbing problem.gif
The mountain climbing problem

Proof

Euler's proof of the degree sum formula uses the technique of double counting: he counts the number of incident pairs where is an edge and vertex is one of its endpoints, in two different ways. Vertex belongs to pairs, where (the degree of ) 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 . 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. [8] 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 , 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. [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. [17]

In special classes of graphs

Clebsch Lombardi.svg
The Clebsch graph, regular of degree five, has an even number of vertices (16) and a number of edges (40) that is a multiple of five.
Rhombicdodecahedron.jpg
The rhombic dodecahedron is biregular with six vertices of degree four and eight vertices of degree three; 6 × 4 = 8 × 3 = 24, its number of edges.

Regular graphs

The degree sum formula implies that every -regular graph with vertices has edges. [18] Because the number of edges must be an integer, it follows that when is odd the number of vertices must be even. [19] Additionally, for odd values of , the number of edges must be divisible by . [20]

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. [21] For biregular graphs, with a partition of the vertices into subsets and with every vertex in a subset having degree , it must be the case that ; both equal the number of edges. [22]

Infinite graphs

An infinite graph with only one odd vertex Infinite graph one direction.svg
An infinite graph with only one odd vertex

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

Subgraphs

By a theorem of Gallai the vertices of any graph can be decomposed as where has all degree even and has all degree odd with even by the handshaking lemma. In 1994 Yair Caro [24] proved that and in 2021 a preprint by Ferber Asaf and Michael Krivelevich showed that . [25] [26]

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; [27] 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. [28]

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

Notes

  1. 1 2 Hein, James L. (2015), "Example 3: The Handshaking Problem", Discrete Structures, Logic, and Computability, Jones & Bartlett Publishers, p. 703, ISBN   9781284070408
  2. 1 2 3 Gunderson, David S. (2014), Handbook of Mathematical Induction: Theory and Applications, CRC Press, p. 240, ISBN   9781420093650
  3. 1 2 Euler, L. (1736), "Solutio problematis ad geometriam situs pertinentis" (PDF), 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. 1 2 Higgins, Peter M. (1998), Mathematics for the Curious, Oxford University Press, p. 201, ISBN   9780192880727
  5. 1 2 3 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. 1 2 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 July 21, 2019. 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, 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. Caro, Yair (15 September 1994). "On induced subgraphs with odd degrees". Discrete Mathematics. 132 (1–3): 23–28. doi: 10.1016/0012-365X(92)00563-7 .
  25. Ferber, Asaf; Krivelevich, Michael (2020). "Every graph contains a linearly sized induced subgraph with all degrees odd". arXiv: 2009.05495 [math.CO].
  26. Honner, Patrick (2022-03-24). "What a Math Party Game Tells Us About Graph Theory". Quanta Magazine. Retrieved 2022-03-27.
  27. 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
  28. 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, S2CID   14102058, ECCC   TR05-140
  29. 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
  30. 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, S2CID   8111195

Related Research Articles

<span class="mw-page-title-main">Four color theorem</span> Statement in mathematics

In mathematics, the four color theorem, or the four color map theorem, states that no more than four colors are required to color the regions of any map so that no two adjacent regions have the same color. Adjacent means that two regions share a common boundary curve segment, not merely a corner where three or more regions meet. It was the first major theorem to be proved using a computer. Initially, this proof was not accepted by all mathematicians because the computer-assisted proof was infeasible for a human to check by hand. The proof has gained wide acceptance since then, although some doubters remain.

<span class="mw-page-title-main">Regular graph</span> Graph where each vertex has the same number of neighbors

In graph theory, a regular graph is a graph where each vertex has the same number of neighbors; i.e. every vertex has the same degree or valency. A regular directed graph must also satisfy the stronger condition that the indegree and outdegree of each internal vertex are equal to each other. A regular graph with vertices of degree k is called a k‑regular graph or regular graph of degree k. Also, from the handshaking lemma, a regular graph contains an even number of vertices with odd degree.

In mathematics, and more specifically in algebraic topology and polyhedral combinatorics, the Euler characteristic is a topological invariant, a number that describes a topological space's shape or structure regardless of the way it is bent. It is commonly denoted by .

<span class="mw-page-title-main">Cycle (graph theory)</span> Trail in which only the first and last vertices are equal.

In graph theory, a cycle in a graph is a non-empty trail in which only the first and last vertices are equal. A directed cycle in a directed graph is a non-empty directed trail in which only the first and last vertices are equal.

<span class="mw-page-title-main">Bipartite graph</span> Graph divided into two independent sets

In the mathematical field of graph theory, a bipartite graph is a graph whose vertices can be divided into two disjoint and independent sets and , that is every edge connects a vertex in to one in . Vertex sets and are usually called the parts of the graph. Equivalently, a bipartite graph is a graph that does not contain any odd-length cycles.

<span class="mw-page-title-main">Hamiltonian path</span> Path in a graph that visits each vertex exactly once

In the mathematical field of graph theory, a Hamiltonian path is a path in an undirected or directed graph that visits each vertex exactly once. A Hamiltonian cycle is a cycle that visits each vertex exactly once. A Hamiltonian path that starts and ends at adjacent vertices can be completed by adding one more edge to form a Hamiltonian cycle, and removing any edge from a Hamiltonian cycle produces a Hamiltonian path. Determining whether such paths and cycles exist in graphs are NP-complete.

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. In this technique, which van Lint & Wilson (2001) call "one of the most important tools in combinatorics", one describes a finite set from two perspectives leading to two distinct expressions for the size of the set. Since both expressions equal the size of the same set, they equal each other.

This is a glossary of graph theory. Graph theory is the study of graphs, systems of nodes or vertices connected in pairs by lines or edges.

<span class="mw-page-title-main">Pick's theorem</span> Formula for area of a grid polygon

In geometry, Pick's theorem provides a formula for the area of a simple polygon with integer vertex coordinates, in terms of the number of integer points within it and on its boundary. The result was first described by Georg Alexander Pick in 1899. It was popularized in English by Hugo Steinhaus in the 1950 edition of his book Mathematical Snapshots. It has multiple proofs, and can be generalized to formulas for certain kinds of non-simple polygons.

<span class="mw-page-title-main">Eulerian path</span> Trail in a graph that visits each edge once

In graph theory, an Eulerian trail is a trail in a finite graph that visits every edge exactly once. Similarly, an Eulerian circuit or Eulerian cycle is an Eulerian trail that starts and ends on the same vertex. They were first discussed by Leonhard Euler while solving the famous Seven Bridges of Königsberg problem in 1736. The problem can be stated mathematically like this:

<span class="mw-page-title-main">Sperner's lemma</span> Theorem on triangulation graph colorings

In mathematics, Sperner's lemma is a combinatorial result on colorings of triangulations, analogous to the Brouwer fixed point theorem, which is equivalent to it. It states that every Sperner coloring of a triangulation of an -dimensional simplex contains a cell whose vertices all have different colors.

In the mathematical discipline of graph theory, the line graph of an undirected graph G is another graph L(G) that represents the adjacencies between edges of G. L(G) is constructed in the following way: for each edge in G, make a vertex in L(G); for every two edges in G that have a vertex in common, make an edge between their corresponding vertices in L(G).

<span class="mw-page-title-main">Edge coloring</span> Problem of coloring a graphs edges such that meeting edges do not match

In graph theory, an edge coloring of a graph is an assignment of "colors" to the edges of the graph so that no two incident edges have the same color. For example, the figure to the right shows an edge coloring of a graph by the colors red, blue, and green. Edge colorings are one of several different types of graph coloring. The edge-coloring problem asks whether it is possible to color the edges of a given graph using at most k different colors, for a given value of k, or with the fewest possible colors. The minimum required number of colors for the edges of a given graph is called the chromatic index of the graph. For example, the edges of the graph in the illustration can be colored by three colors but cannot be colored by two colors, so the graph shown has chromatic index three.

<span class="mw-page-title-main">Snark (graph theory)</span> 3-regular graph with no 3-edge-coloring

In the mathematical field of graph theory, a snark is an undirected graph with exactly three edges per vertex whose edges cannot be colored with only three colors. In order to avoid trivial cases, snarks are often restricted to have additional requirements on their connectivity and on the length of their cycles. Infinitely many snarks exist.

<span class="mw-page-title-main">Degree (graph theory)</span> Number of edges touching a vertex in a graph

In graph theory, the degree of a vertex of a graph is the number of edges that are incident to the vertex; in a multigraph, a loop contributes 2 to a vertex's degree, for the two ends of the edge. The degree of a vertex is denoted or . The maximum degree of a graph , denoted by , and the minimum degree of a graph, denoted by , are the maximum and minimum of its vertices' degrees. In the multigraph shown on the right, the maximum degree is 5 and the minimum degree is 0.

In graph theory, a part of discrete mathematics, the BEST theorem gives a product formula for the number of Eulerian circuits in directed (oriented) graphs. The name is an acronym of the names of people who discovered it: de Bruijn, van Aardenne-Ehrenfest, Smith and Tutte.

The discharging method is a technique used to prove lemmas in structural graph theory. Discharging is most well known for its central role in the proof of the four color theorem. The discharging method is used to prove that every graph in a certain class contains some subgraph from a specified list. The presence of the desired subgraph is then often used to prove a coloring result.

<span class="mw-page-title-main">Grinberg's theorem</span> On Hamiltonian cycles in planar graphs

In graph theory, Grinberg's theorem is a necessary condition for a planar graph to contain a Hamiltonian cycle, based on the lengths of its face cycles. If a graph does not meet this condition, it is not Hamiltonian. The result has been widely used to prove that certain planar graphs constructed to have additional properties are not Hamiltonian; for instance it can prove non-Hamiltonicity of some counterexamples to Tait's conjecture that cubic polyhedral graphs are Hamiltonian.

The Erdős–Gallai theorem is a result in graph theory, a branch of combinatorial mathematics. It provides one of two known approaches to solving the graph realization problem, i.e. it gives a necessary and sufficient condition for a finite sequence of natural numbers to be the degree sequence of a simple graph. A sequence obeying these conditions is called "graphic". The theorem was published in 1960 by Paul Erdős and Tibor Gallai, after whom it is named.

<span class="mw-page-title-main">Petersen's theorem</span>

In the mathematical discipline of graph theory, Petersen's theorem, named after Julius Petersen, is one of the earliest results in graph theory and can be stated as follows:

Petersen's Theorem. Every cubic, bridgeless graph contains a perfect matching.