In a simple graph consisting of ‘n’ vertices, maximum possible number of edges is n(n-1)/2
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 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 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 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.
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
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.