Let $G$ be a graph with $40$ vertices and $E$ edges.

a) If $G$ is connected, what is the minimum possible value of $E$?
b) What is the minimum value of $E$ that guarantees that $G$ is connected?

I thought that the minimum number of edges would be $40C2$ and you would add 1 to guarantee that $G$ is connected...how is this incorrect?

  • $\begingroup$ You are talking about simple graphs (no loops or multiple edges), right? In that case, with $40$ vertices, $\binom{40}2$ is the maximum possible number of edges, with every vertex connected to every other vertex, and there's no place to add another edge. $\endgroup$ – bof Jun 13 '15 at 20:51
  • $\begingroup$ Are we making some assumptions to answer (b)? I could just put a bunch of loops on one vertex, and then there would be no number of edges which would guarantee that $G$ is connected $\endgroup$ – Alex G. Jun 13 '15 at 20:51
  • $\begingroup$ $\binom{40}{2}$ is the maximum number of possible edges in a graph with 40 vertices. This graph would be complete, you could not "add one" to that condition. Plus, it's not the answer. $\endgroup$ – KidA424 Jun 13 '15 at 20:52
  • 1
    $\begingroup$ I suppose you've tried this for smaller numbers of vertices than $40,$ right? (If not, why not??) So what answers do you get for (a) and (b) for $3,4,5,6,7$ vertices? $\endgroup$ – bof Jun 13 '15 at 20:53
  • 1
    $\begingroup$ @TravisJ: I am not sure your comment about two disjoint $K_{20}$s is very helpful. Consider adding an isolated vertex to a $K_{39}$. $\endgroup$ – Rob Arthan Jun 13 '15 at 22:18

Your Answer

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

Browse other questions tagged or ask your own question.