Question

What is the maximum number of edges in a simple graph? If you got n verses, what’s the maximum number of edges? Explain in your own words.

Answer 1

The maximum number of edges in a undirected graph is:- n(n-1)/2

The maximum number of edges in a directed graph is twice of undirected graph:- n(n-1)

Now, to prove this let us consider n numbers of vertices. From the first vertices there are total number of n-1 edges to each vertices. For the second vertices there are n-2 edges to other vertices because there is already an edge between first and second vertices. So on for all the other vertices.

Hence ,total number of edges are sum of all the edges to each vertices

(n-1)+(n-2)+(n-3)+.......................+3+2+1+0

For this sum of this expression

:-n/2(first+last)

:- n/2(n-1+0)

:- n/2(n-1)

Hence total number of edges in undirected graph are n(n-1)/2