Handshaking Theorem

The Handshaking Lemma, also known as the Handshaking Theorem, is a fundamental result in graph theory that describes the relationship between the degrees of vertices and the number of edges in a graph. The theorem is named after the common practice of handshaking, where two people shake hands, each person using one hand. This handshake involves two vertices, each with degree one.

The Handshaking Lemma states that in any undirected graph, the sum of the degrees of all the vertices is equal to twice the number of edges. In other words, if we add up the degree of each vertex (which is the number of edges incident to that vertex), the sum is equal to twice the number of edges in the graph.

For example:-

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.

To prove the Handshaking Lemma, let G = (V, E) be an undirected graph with n vertices and m edges. Each edge e = {u, v} in E is incident to two vertices u and v, so we can count the edges in two different ways: either by summing the degrees of all the vertices, or by counting each edge twice (once for each of its endpoints).

Summing the degrees of all the vertices, we get:

sum(deg(v)) = deg(v1) + deg(v2) + ... + deg(vn)

Counting each edge twice, we get:

2m = |{e in E}| + |{e in E}| = sum(deg(v)),

where |{e in E}| denotes the number of elements in the set E. The first equality counts each edge in the set E once, while the second equality counts each endpoint of each edge in E, giving a total of 2m.

Combining these two equalities, we get:

sum(deg(v)) = 2m

This is the Handshaking Lemma.

The Handshaking Lemma has many useful applications in graph theory. For example, it can be used to prove the existence of vertices of the same degree in a graph, or to show that a graph has an even number of vertices with odd degree. It can also be used to calculate the average degree of a vertex in a graph, which is given by 2m/n, where m is the number of edges and n is the number of vertices.

In addition to its theoretical applications, the Handshaking Lemma has practical implications in computer science and engineering. For example, it can be used to design efficient algorithms for network routing, load balancing, or resource allocation. The lemma can also be used to analyze the performance of distributed systems, such as peer-to-peer networks or cloud computing platforms.

Despite its simplicity, the Handshaking Lemma is a powerful tool in graph theory and has many important applications. It provides a basic understanding of the relationship between the degrees of vertices and the number of edges in a graph, and can be used to derive many useful results in graph theory and related fields.

For another puzzle of graph theory click here.