CareerCup

Just exclude one vertice and then connect all the n-1 vertices, it will be (n-1)C2 i.e. (n-1)(n-2)/2.

is it ((n-2)*(n-1)/2)

Complete graph -- one to one connection for n vertices needs 1+2+3+..+(n-1) edges.
which is (n-1)*n/2 edges...
Here we need to keep one vertex aside, and completely connect n-1 vertices..
which comes to (n-1)*(n-2)/2 edges..

Formula - 1+2+3+..+n = n*(n+1)/2

A graph is called as disconnected if there exists at least one pair of vertices (u,v) such that there is not any path between them.
To make the above definition correct, Separate one vertex & join the remaining n-1 vertices.
So, it can be done in n-1C2=(n-1)*(n-2)/2

Complete graph -- one to one connection for n vertices needs 1+2+3+..+(n-1) edges.
which is (n-1)*n/2 edges...
Here we need to keep one vertex aside, and completely connect n-1 vertices..
which comes to (n-1)*(n-2)/2 edges..

Formula - 1+2+3+..+n = n*(n+1)/2

when n is even its n-2 and when n is odd its [n/2] (upper ceiling function)

in any simple graph having n vertex max edges can be (n)C2 now we need max edges with a disconnected graph.

let us assume there are “X” vertex in one side & (n-x) vertex on other side.

We can say that max edges in the graph would be xC2 & (n-x)C2

Total edges in graph are P = xC2+(n-x)C2 which we need to maximize.

If we solve it by max & min concept we will get x =(n/2)

Which means we should divide it in two halves.

Leave one vertex and connect rest n-1 vertices to each other. And that can be done in (n-1)! ways. So, the max edges possible are (n-1)!