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

Question

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.

Answer 1

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?

Answer 2

The formula is worthless without a proof.

Suppose we have a graph on $n$ vertices which is not connected. Then it is possible to divide into two disjoint subgraphs, say one with $i$ vertices and another with $n - i$ vertices. The component with $i$ vertices has at most $i (i - 1)/2$ edges, while the component with $n - i$ vertices has at most $(n - i) (n - i - 1)/2$ edges (this happens when the two components are complete graphs). Therefore we have at most $$i (i - 1)/2 + (n - i) (n - i - 1)/2 = i (i - n) + n (n - 1) / 2$$ edges. The number of edges has a fixed part $n (n - 1) / 2$ and a variable part $i (i - n)$ which depends on $i$. We would like an upper bound for the variable part. By using the method of completing the square we can write it as $$i (i - n) = (i - n/2)^2 - n^2/4.$$ As a function of $i$ this is a parabola whose minimum is at $i = n/2$. Thus, to get the largest possible value in the allowed range $0 < i < n$ we should plug in the value of $i$ which is furthest away from the minimum. This happens when $i = 1$ or $i = n - 1$, and both give us the same estimate: $$i (i - n) = (i - n/2)^2 - n^2/4 \leq (1 - n/2)^2 - n^2/4 = 1 - n.$$ We may thus estimate the number of edges as $$i (i - n) + n (n - 1)/2 \leq (1 - n) + n (n - 1)/2 = (n-1)(n-2)/2$$ We conclude that the number of edges in a disconnected graph with $n$ vertices is at most $(n - 1)(n - 2)/2$. This is a tight upper bound which is achieved when one of the subgraphs is a point and the other a complete graph on $n-1$ vertices.