# How many edges are needed for a graph with $40$ vertices to be (guaranteed) connected?

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?

• 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. – bof Jun 13 '15 at 20:51
• 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 – Alex G. Jun 13 '15 at 20:51
• $\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. – KidA424 Jun 13 '15 at 20:52
• 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? – bof Jun 13 '15 at 20:53
• @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}$. – Rob Arthan Jun 13 '15 at 22:18