Handshaking Theorem | Graph Theory Theorems

Theorem-

 

In a simple graph consisting of ‘n’ vertices, maximum possible number of edges is n(n-1)/2

 

Proof-

 

Let us prove it using “Handshaking Lemma”.

Considering the vertices as people and the edges as handshakes, we could ask how many handshakes are possible among ‘n’ people if every pair of people shakes hands exactly once.

Let each person give handshake to all other people one by one without any duplication.

 

Person-1:

 

Person-1 handshakes with all other (n-1) people, so in total (n-1) handshakes are done.

Now, let us remove Person-1 from the group again to eliminate duplicate handshakes when we select other people.

 

Person-2:

 

Person-2 handshakes with all other (n-2) people, so in total (n-2) handshakes are done (n-2 is since we removed 1 person)

Now, let us remove Person-2 from the group to eliminate duplicate handshakes when we select other people.

 

Person-3:

 

Person-3 handshakes with all other (n-3) people, so in total (n-3) handshakes are done (n-3 is since we removed 2 persons)

Now, let us remove Person-3 from the group to eliminate duplicate handshakes when we select other people.

 

Continuing in this manner,

At last, we get 1 handshake from last two people.

So, we get (n-1), (n-2), (n-3), …., 1 handshakes without any duplication.

 

Now,

Sum of all handshakes = (n-1) + (n-2) + (n-3) + …. + 1

 = [(n(n+1)) / 2] – n      ( since n+(n-1)+(n-2)+….+1 = (n(n+1))/2 )

 = [n(n-1)] / 2

 = nC2

 

Thus, Maximum possible number of edges in a simple graph is given by n(n-1) / 2. Hence, proved.

 

Get more notes and other study material of Graph Theory.

Watch video lectures by visiting our YouTube channel LearnVidFun.

Summary
Handshaking Theorem | Graph Theory Theorems
Article Name
Handshaking Theorem | Graph Theory Theorems
Description
Handshaking Theorem in Graph Theory states- In a simple graph consisting of 'n' vertices, maximum possible number of edges is n(n-1)/2. Handshaking lemma is used to prove the theorem.
Author
Publisher Name
Gate Vidyalay
Publisher Logo
Liked this article? Share it with your friends and classmates now-