Use of Handshaking Lemma in Tree Data Structure
In laymen's terms, The handshaking lemma states that if a group of people shakes hands, it is always the case that an even number of people have shaken an odd number of hands.
A formal definition would be, The handshake lemma deals with an undirected graph. The odd degree is always encompassed by the even number of vertices in every finite undirected graph. The degree sum formula shows the consequences as a handshaking lemma.
Sum of the degree of all vertices = 2 x Number of edges
Proof of Statement
People are represented as nodes on a graph, and a handshake is defined as a line linking them.
We're going to start with no handshakes. So far, 0 persons have shaken the hands of an odd number of people.
Then comes the first handshake. This is a two-person job. After that, they each shake one hand, resulting in two persons shaking an odd number of hands.
Let's take a look at what happens with each new handshake.
Case No. 1
Assume two people are involved, each of whom has shaken an even number of hands. They each boost their handshake count by one when they shake hands, bringing the number of persons who have shaken an odd number of hands to two.
Case No. 2
What if they've both shaken a considerable number of hands? Then they both shake an even number of hands, reducing the number of persons who have shaken an odd number of hands by two.
Case No. 3
What if one of them has shaken an even number of hands while the other has shaken an odd number? The individual who has shaken an even number of hands now shakes an odd number of hands, giving us a plus one. However, the person who had shaken an odd number of hands has now shaken an even number of hands, resulting in a -1 to our count. As a result, the net change is zero.
We can now finish our proof. One by one, we add handshakes to our handshake graph. Every time the number of persons who have shaken an odd number of hands changes by 2, 0, or -2, the number of people who have shaken an even number of hands changes by 2, 0, or -2. As a result, whether the number is even or odd is preserved each time we add a new handshake to our graph. It is even after we have included all the handshakes since it starts at 0 (even).
Problem
G is a simple graph with 24 edges and a degree of 4 for each vertex. Determine the total number of vertices.
Solution
The number of edges is set to 24.
Each vertex's degree is equal to 4.
Let n be the total number of vertices in the graph.
Sum of the degree of all vertices = 2 x Number of edges( according to the Handshaking Theorem)
We get n x 4 = 2 x 24 by substituting the variables.
n = 2 x 6 n = 12 n = 2 x 6 n = 2 x 6 n = 2 x 6
As a result, the graph's number of vertices equals 12.
Frequently Asked Questions
Why is it called the handshaking lemma?
The name "handshaking lemma" comes from the analogy of a handshake between two people representing an edge in the graph. When two people shake hands, each person's hand represents a vertex, and the handshake represents an edge between them.
What is an example of Handshaking Theorem?
Consider a simple undirected graph with four vertices and five edges. Applying the handshaking lemma, we can see that the sum of the degrees of all vertices equals twice the number of edges: 1 + 2 + 2 + 1 = 6 = 2 x 5.
How do you calculate handshaking lemma?
To calculate the handshaking lemma, you simply sum the degrees of all vertices in a graph and then divide the result by 2. The formula can be written as:
∑deg(v) = 2|E|
where v is vertex v, and |E| is the number of edges.
What is Handshaking Lemma with example?
The Handshaking Lemma in graph theory states that the sum of the degrees of all vertices in an undirected graph is twice the number of edges. For example, in a graph with three vertices, if vertex A is connected to vertex B and vertex C, the degrees are 2, 1, and 1, respectively. The sum of degrees is 2 + 1 + 1 = 4, which is twice the number of edges (2).
Conclusion
In this blog, we discussed the handshaking lemma and use of it. We briefly discussed the proof of statement and multiple cases. We then understood this through a problem.
Here are more articles for rescue. Here are more articles for rescue.
Refer to our guided paths on Coding Ninjas Studio to learn more about DSA, Competitive Programming, JavaScript, System Design, etc.
Do upvote our blog to help other ninjas grow.
Happy Learning!
24+ registered 
