Let $G$ be a simple graph with $v$ vertices and $e$ edges. If $e < v-1$, then there is no spanning tree of $G$ (for a tree over $v$ vertices requires exactly $v-1$ edges), and hence $G$ is disconnected. If $e> \frac{(v-1)(v-2)}{2}$, then $G$ must have only one connected component (in other words, $G$ is connected). Otherwise, let $k>1$ be the number of connected component of $G$, we must have \[\frac{(v-1)(v-2)}{2} < e \leq (k-1)\binom{1}{2} + \binom{v-(k-1)}{2} \leq \binom{v-1}{2}\,,\] a contradiction. PS: Haven't thought about this question into details, but it sounds interesting: what is the smallest value of $e$ such that we can travel between any two towns by at least two different paths? I think $\binom{v-1}{2}+2$ is enough. (By a path between $A$ and $B$, I mean a sequence of vertices $\left(V_1,V_2,\ldots,V_n\right)$ such that $V_1=A$ and $V_2=B$, that all $V_i$'s are distinct, and that $V_iV_{i+1}$ is an edge of the graph for every $i=1,2,\ldots,n-1$.)