1
$\begingroup$

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?

$\endgroup$
  • $\begingroup$ 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. $\endgroup$ – Juho Jan 30 '17 at 8:02
  • $\begingroup$ In other words, they should've had "necessarily" between "be" and "connected". ​ ​ $\endgroup$ – user12859 Jan 30 '17 at 8:05
  • $\begingroup$ 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. $\endgroup$ – anir Jan 30 '17 at 8:08
  • $\begingroup$ It should probably read "the minimum number of edges for a $n$ vertex graph to be necessarily connected" $\endgroup$ – adrianN Jan 30 '17 at 8:15
1
$\begingroup$

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

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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