# Find the maximum number of edges in the graph

algorithmedge-detectiongraph

There are 'n' vertices and 0 edges of an undirected graph. What can be the maximum number of edges that we can draw such that the graph remains disconnected.

I have made the solution that we can exclude one vertex and can find the maximum number of edges between n-1 vertices of undirected graph, so that the graph still remains disconnected.

which is n(n-1)/2 for n vertices and will be (n-1)(n-2)/2 for n-1 vertices.
Can there be a better solution?

#### Best Solution

You can resolve this using analysis. Take your idea and generalize it. You divide the n vertices in two groups , of size `x` and `n-x`. Now the number of edges is a function of `x`, expressed by

``````  f(x)= x(x-1)/2 + (n-x)(n-x-1)/2
f(x) = 1/2(2x^2 - 2nx +n^2 - n)
``````

The value which maximize this function is the partition size you want. If you make calculation you find that it decrease from `x=0` to `x=n/2`, then increase to `x=n`. As x = 0 or x = n means the graph is collected, you take the next greatest value which is `x=1`. So your intuition is optimal.