Find the maximum number of edges in the graph

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.

Your solution should be the best solution.

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