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

ignougroup
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.