Code360 powered by Coding Ninjas X Naukri.com. Code360 powered by Coding Ninjas X Naukri.com
Table of contents
1.
Introduction
2.
What is Handshaking Lemma?
3.
Use of Handshaking Lemma in Tree Data Structure
4.
Proof of Statement
4.1.
Case No. 1
4.2.
Case No. 2
4.3.
Case No. 3
5.
Problem
6.
Solution
7.
Frequently Asked Questions
7.1.
Why is it called the handshaking lemma?
7.2.
What is an example of Handshaking Theorem?
7.3.
How do you calculate handshaking lemma?
7.4.
What is Handshaking Lemma with example?
8.
Conclusion
Last Updated: Mar 27, 2024
Medium

Handshaking Lemma

Master Power BI using Netflix Data
Speaker
Ashwin Goyal
Product @
18 Jun, 2024 @ 01:30 PM
Handshaking Lemma

Introduction

The Handshaking Theorem is also known as the Sum of Degree Theorem or the Handshaking Lemma.

The Handshaking Theorem in Graph Theory argues that in any graph; The sum of all the vertices' degrees equals twice the number of edges.

Handshaking Theorem in Graph

 

What is Handshaking Lemma?

The Handshaking Lemma is a fundamental principle in graph theory that relates the number of edges in an undirected graph to the degrees of its vertices. According to this lemma, the sum of the degrees of all the vertices in a graph is equal to twice the number of edges. Although this might appear to be a simple result, it has significant practical applications in diverse fields such as computer science, transportation planning, and social network analysis. For instance, it can be used to determine the minimum number of colours required to colour the vertices of a graph so that no two adjacent vertices have the same color. It can also help in analysing the connectivity of a network and identifying critical vertices or edges that, if removed, would disconnect the network.

The Handshaking Lemma refers to a fundamental concept in graph theory. The Handshaking Lemma states that in any undirected graph, the sum of the degrees of all the vertices equals twice the number of edges in the graph. In other words, if you add up the number of connections (edges) at each vertex (degree), the total will be twice the number of edges. The Handshaking Lemma is not hard to prove. A corollary of the Handshaking Lemma is that the number of odd-degree vertices in any graph must be even. 

Get the tech career you deserve, faster!
Connect with our expert counsellors to understand how to hack your way to success
User rating 4.7/5
1:1 doubt support
95% placement record
Akash Pal
Senior Software Engineer
326% Hike After Job Bootcamp
Himanshu Gusain
Programmer Analyst
32 LPA After Job Bootcamp
After Job
Bootcamp

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!

Live masterclass