Take the 2-minute tour ×
Computer Science Stack Exchange is a question and answer site for students, researchers and practitioners of computer science. It's 100% free, no registration required.

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.

share|improve this question

marked as duplicate by Joe, Jernej, A.Schulz, AJed, Luke Mathieson Dec 17 '12 at 0:47

This question has been asked before and already has an answer. If those answers do not fully address your question, please ask a new question.

2  
Your reasoning is correct, did your teacher just copy of that website? Just to push it a bit further, it's not even possible for a simple, undirected graph to have $\frac{n(n-1)}{2}+1$ edges. –  Luke Mathieson Dec 13 '12 at 11:10
    
I just want to say that there is the possibility that I wrong to take notes at lesson. this explanataion was "oral" not written, so it could be my fault. I take this opportunity to thank you. –  newbie Dec 13 '12 at 12:01
    
No problem, don't forget to accept the best answer :) –  Luke Mathieson Dec 13 '12 at 13:36

2 Answers 2

up vote 4 down vote accepted

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?
share|improve this answer
    
As another side note, perhaps they accidentally used the formula for the sum of the first $n-1$ integers, instead of the closed form of $\binom{n-1}{2}$, they're annoyingly similar. –  Luke Mathieson Dec 13 '12 at 11:45
2  
Your teacher obviously made an off-by-one error. Most teachers know very well how easy it is to make a mistake, and will not mind being corrected. But some will mind being corrected by a jerk, so I would advise that you do it politely. Also, if the teacher disagrees, do not just cave in. Argue your position. That is what school is for, to argue with your teachers. How else are you going to learn independent thinking? –  Andrej Bauer Dec 13 '12 at 13:56
    
Also, I have just seen formulas here, without any proofs. You should figure out how to prove that your result is correct. Math is not a matter of opinion. –  Andrej Bauer Dec 13 '12 at 13:57

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.

share|improve this answer
    
This is better answer than other one but still you should prove why: "the variable part is always negative and is largest when $i=n−1$". –  user742 Dec 13 '12 at 14:32
    
How true! I included a proof, and when doing so discovered a flaw in my argument! The variable part is largest when $i = n - 1$ or $i = 1$. And that is not surprising, given that we have a symmetry between the two disjoing subgraphs. –  Andrej Bauer Dec 13 '12 at 15:44
    
The moral of the story: a good teacher will gladly admit a mistake, and make everyone learn from it. –  Andrej Bauer Dec 13 '12 at 15:45
    
Indeed ........ –  user742 Dec 13 '12 at 16:04

Not the answer you're looking for? Browse other questions tagged or ask your own question.