Using a small modification to Turáns theorem we can find the minimum amount of edges a graph $G$ on $n$ vertices must have so it does not have an independent set of size $k$. Is there a similar result if we add the restriction that $G$ is a connected graph?



Turan's theorem for connected graphs?
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. 


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.


