How many edges must a graph with N vertices have in order to guarantee that it is connected?

ignougroup
Question Detail: 

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

At lesson my teacher said that a graph with $n$ vertices to be certainly connected should have
$ {frac{n(n-1)}{2}+1 space }$ edges showing that (the follow is taken from the web but says the same thing):

The non-connected graph on n vertices with the most edges is a complete graph on $n-1$ vertices and one isolated vertex. So you must have $ 1+ {frac{n(n-1)}{2} space}$ edges to guarantee connectedness.

My idea: a complete graph $K_{n-1}$ with $n-1$ vertices has ${n-1 choose 2}$edges, so ${frac{(n-1)*(n-2)}{2}}$ edges, added to the edge to connect the complete graph to the isolate vertex, so shouldn’t be ${frac{(n-1)*(n-2)}{2}}+1$ edges? What am I doing wrong? Thanks.

Asked By : newbie
Best Answer from StackOverflow

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

Answered By : Luke Mathieson

Don’t know why I didn’t just give an answer, rather than a comment, but for posterity: Your reasoning is correct, the $n$ vertex graph with the maximal number of edges that is still disconnected is a $K_{n-1}$ with an additional isolated vertex. Hence, as you correctly calculate, there are $binom{n}{2} = frac{(n-1)(n-2)}{2}$ edges. Adding any possible edge must connect the graph, so the minimum number of edges needed to guarantee connectivity for an $n$ vertex graph is $frac{(n-1)(n-2)}{2}+1$. Contrary to what your teacher thinks, it’s not possible for a simple, undirected graph to even have $frac{n(n-1)}{2}+1$ edges (there can only be at most $binom{n}{2} = frac{n(n-1)}{2}$ edges). The meta-lesson is that teachers can also make mistakes, or worse, be lazy and copy things from a website. For an extension exercise if you want to show off when you tell the teacher they’re wrong, how many edges do you need to guarantee connectivity (and what’s the maximum number of edges) in a

  1. Simple, directed graph?
  2. A directed graph that allows self loops?