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?
My initial thought is that the minimum number of edges would be $40C2$ and you would add 1 to guarantee that $G$ is connected. This proved to be incorrect. Hints or the solution would be appreciated!
For b), if the graph is disconnected, no vertex can have more than $39$ neighbors. In the complete graph on $39$ vertices, each vertex has exactly $39$ neighbors, so a $K_{{{39}}}$ plus a disconnected vertex is a disconnected graph, while adding an edge creates a connected graph (one vertex now has $40$ neighbors). This graph has $\binom{39}{2}+1 = \frac{38\cdot 39}{2} + 1$ edges.