Just a partial answer, expanding Tony's:

The statement is true for $n=2k$ (i.e. you need exactly $(2k-1)$ edges to avoid an independent set of size $k+1$ in a connected graph), and the extremal graphs are exactly the trees with a perfect matching (contrary to what Tony stated).

Proof: Clearly, you need $2k-1$ edges to make it connected. And $2k-1$ are sufficient, take any tree without an independence set of size $k+1$ (a path would do).

It remains the classification. Clearly we only need to consider trees.

If a tree on $2k$ vertices has no independent set of size $k+1$, then it has a perfect matching:
proof by induction on $k$. $k=1$ is trivial. For $k>1$, consider a non-leaf $v$. If we delete $v$, the remaining forest has exactly one odd component $T_v$, all other components are even. Otherwise, pick the bigger part in the bipartition of each component, and you end up with an independent set of size $k+1$. By the same reason, each component of size $2k'$ has independence number $k'$, and thus by induction a perfect matching. It remains to consider $T_v+ v$. If this tree had an independent set of size larger then half, we could combine this with the parts in the other components not incident to $v$ to create an independence set of size $k+1$, again a contradiction. So, again by induction, $T_v+v$ has a perfect matching.

If a tree on $2k$ vertices has a perfect matching, then it has no independent set of size $k+1$: 
This follows trivially from PHP.