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.

A Riddle whose answer is no answer

The Konigsberg Bridge Problem is a famous mathematical puzzle that was first posed by Leonhard Euler in the 18th century. Euler was a Swiss mathematician who is considered one of the most influential mathematicians of all time, and his solution to the Konigsberg Bridge Problem is considered a landmark result in the field of graph theory.

The problem is set in the city of Konigsberg, which was situated on both sides of the Pregel River and included two large islands connected to each other and the mainland by seven bridges. The puzzle asked whether it was possible to walk around the city, crossing each of the seven bridges exactly once, and return to the starting point.

Let's take some time before seen the answer of this riddle and try it once by yourself.

Euler approached the problem by introducing the concept of a graph, which is a mathematical representation of a set of objects (called vertices) and the connections between them (called edges). In the case of the Konigsberg Bridge Problem, the vertices represented the land masses and the edges represented the bridges. Euler's first step was to simplify the problem by abstracting away the details of the city and focusing only on the connections between the land masses.

Euler then showed that the problem was impossible to solve by proving that any path that begins at an odd-numbered vertex must end at an odd-numbered vertex, and any path that begins at an even-numbered vertex must end at an even-numbered vertex. Since Konigsberg had four odd-numbered vertices, it was impossible to construct a path that crossed each bridge exactly once and returned to the starting point.

Euler's proof is based on a fundamental property of graphs, which is that the sum of the degrees of all the vertices in a graph is equal to twice the number of edges. In the case of the Konigsberg Bridge Problem, each vertex has an odd degree, because it is connected to an odd number of bridges. Since the sum of the degrees of all the vertices is an odd number, it follows that the number of edges must be an odd number as well. However, in order to cross each bridge exactly once and return to the starting point, the number of edges must be an even number (because each bridge is used twice, once in each direction). Therefore, it is impossible to construct such a path.

Euler's solution to the Konigsberg Bridge Problem is considered a landmark result in the field of graph theory because it introduced the concept of a graph and laid the foundations for a whole branch of mathematics. Graph theory has applications in computer science, engineering, operations research, social sciences, and many other fields. For example, graphs can be used to model complex systems, such as social networks, transportation networks, or electrical circuits. Graph algorithms can be used to find optimal paths, to identify clusters, or to detect anomalies in large datasets.

The Konigsberg Bridge Problem also has broader implications for mathematical reasoning and problem-solving. Euler's solution relied on his ability to abstract away the details of the problem and to focus on the underlying structure. By introducing the concept of a graph, Euler was able to generalize the problem and to develop a general method for solving similar problems. This ability to abstract and generalize is a key skill in mathematics, science, and engineering, and is essential for tackling complex problems in the real world.

If you want to read about an another problem(Stable Marriage Problem) and their mathematical solution then click here.