# Minimum number of edges for $n$ vertex graph to be connected

I was reading about connectedness of a graph where I came across following points:

• The $n$ vertex graph with the maximal number of edges that is still disconnected is $K_{n-1}$ (complete graph with $n-1$ vertices) with an additional vertex, which has $\binom{n-1}{2}=\frac{(n-1)(n-2)}{2}$ edges.
• Adding any additional edge must connect the graph. So the minimum number of edges for $n$ vertex graph to be connected is $\frac{(n-1)(n-2)}{2}+1$.

I am ok with the first point but not with the second point. The minimum number of edges for $n$ vertex graph to be connected should be $n-1$. Then how does that second point makes sense? How does the minimum number of edges for $n$ vertex graph to be connected is $\frac{(n-1)(n-2)}{2}+1$? Was the text trying to say something else? Is $\frac{(n-1)(n-2)}{2}+1$ number characterizes/pertains to some other condition on the graph?

• Maybe they mean that if a graph has at least $f(n) = {n-1 \choose 2} + 1$ edges, then it is connected. For instance, $f(5) = 7$, and any 5-vertex graph is connected if it has 7 edges. It would also be connected with a smaller number of edges (i.e., $n-1=4$), as you observe. – Juho Jan 30 '17 at 8:02
• In other words, they should've had "necessarily" between "be" and "connected". ​ ​ – user12859 Jan 30 '17 at 8:05
• Yeah that rephrasing makes sense. They used "minimum", you used "at least". I hope the two are different. To clarify if simple graph with $n$ vertices has at least $\binom{n-1}{2}+1$ edges, then it must be connected. – anir Jan 30 '17 at 8:08
• It should probably read "the minimum number of edges for a $n$ vertex graph to be necessarily connected" – adrianN Jan 30 '17 at 8:15

Likely they mean that if a graph has as at least $f(n) = {n-1 \choose 2}+1$ edges, then it is connected. For instance, $f(5) = 7$, and any 5-vertex graph is connected with 7 edges. However, as you observe, it would also be connected with a smaller number of edges (that is, with $n-1 = 5-1 = 4$ edges).