Every simple undirected graph with more than $(n-1)(n-2)/2$ edges is connected

Question Detail: 

If a graph with $n$ vertices has more than $\frac{(n-1)(n-2)}{2}$ edges then it is connected.

I am a bit confused about this question, since I can always prove that for a graph to connected you need more than $|E|>n-1$ edges.

Asked By : user1675999

Best Answer from StackOverflow

Question Source : http://cs.stackexchange.com/questions/6801

Answered By : Jernej

I am not sure what bothers you but as I see it you are confused about the following two facts

1. If a graph is connected then $e \geq n-1.$

2. If a graph has more than $e > \frac{(n-1)(n-2)}{2}$ then it is connected.

Notice that the implications in 1 and 2 are in opposite directions.

For a proof of 2. you can check out this link.