Minimum number of edges to ensure connectedness Question: Consider a simple graph G with n vertices. What is the minimum number of edges that G must have in order to ensure that it is connected? Justify your answer.
My attempt: Let G = $(V, E)$. Consider a vertex $v \in E$. If G is connected, it is necessary that there is a path from $v$ to each of the remaining $n-1$ vertices. Suppose each path consists of a single edge. This adds up to a minimum of $n-1$ edges. Since $v$ is now connected to every vertex, we see that there is a path between any two vertices $via$ $v$. Therefore G is connected and we are done. So a minimum of $n-1$ edges is required. 
Is this a valid proof? Or am I missing something? 
EDIT: Based on D Poole's answer, I should seek to maximize the expression $\binom{a}{2} + \binom{n-a}{2} + 1$, where $a$ and $n-a$ are the respective number of vertices in the two components.
Let $f(a) = \frac{a(a-1)}{2} + \frac{(n-a)(n-a-1)}{2} = \frac{2a^2 - 2na + n^2 - n}2$
$\frac{df}{da} = \frac{4a - 2n}2$.
Let $\frac{df}{da} = 0.$ Then $a = \frac n2$.
Applying the first derivative test we see that when $a = \frac n2$, $f(a)$ is maximum.
If n is even then there is no problem. If n is odd then should we take $\lfloor \frac n2 \rfloor$ or $\lceil \frac n2 \rceil$?
 A: You show that you can have a graph with $n-1$ edges and be connected. I read the problem as finding the $m$ below:
$$
m= \min\{M: \text{ if }G\text{ is a graph on }n \text{ vertices and }M \text{ edges, then }G \text{ is connected}\}.
$$
Since there are graphs with $n-1$ edges with $n$ vertices that are NOT connected, $m$ should be larger. 
EDIT: How to find this $m$?
A graph $G$ is connected if there is NOT a proper subset $A \subset V(G)$, $1 \leq |A| \leq n-1$ such that there are no edges between $A$ and $A^c$. In particular, for a connected graph $G$ and all subsets of vertices $A$ with $1 \leq |A| \leq n-1$, there is an edge between $A$ and $A^c$. 
For a fixed subset $A$, how many edges can be present so that there are no edges between $A$ and $A^c$? We can have a complete graph on $A$ and a complete graph on $A^c$ but no edges between these two subgraphs. So we can have 
$${|A| \choose 2}+{n-|A| \choose 2}$$
potential edges in this disconnected graph. Conversely, if $G$ has at least 
$${|A| \choose 2}+{n-|A| \choose 2}+1$$
edges, then necessarily there is an edge between $A$ and $A^c$. Consequently, taking the maximum over all $|A|$, we have that
$$
m = \max_a {a \choose 2}+{n-a \choose 2} +1.
$$
When is this expression maximized?
