Graph theory .............111111


#1

how to prove that a complete graph will have maximum number of edges as n(n-1)/2?


#2

There are multiple ways. I will prefer proof by induction.
Suppose n is number of nodes in graph and e is the no of edge in it. Graph is a complete graph.
For n=2, there can be only one edge that will connect both. so e = 1. From formula, n(n-1)/2 = 2(2-1)/2 = 1
For n=3, there will be 3 edges(you can draw and check). From formula, 3(3-1)/2=3

So lets say for n = k also n(n-1)/2 is correct. so e = k(k-1)/2
Now for n = k+1, we are adding one node to existing graph(graph with k nodes). To make it a complete graph, this new node needs to connected to all other nodes which is k. So there will be k extra edges.
e = k(k-1)/2 + k = (k(k-1)+2k)/2 = k(k-1+2)/2 = k(k+1)/2
From formula, e = (k+1)(k+1-1)/2 = (k+1)k/2

Hence proved.