Find the maximum number of edges in the graph

Question

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?

Answer 1

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.

Answer 2

Your solution should be the best solution.

Because any new edge added must have the nth vertex at one end.