Independence Number of A Given Graph Take $i(G)$ to be the independence number of $G$, i.e. the maximum
number of
pairwise nonadjacent vertices in $G.$ I want to show that if $G$ has
$n$ vertices and $\frac{nk}{2}$ edges where $k \geq 1,$
$i(G) \geq \frac{n}{k+1}.$ I'm having difficulties making the
combinatorial argument on this graph. I get that if the graph has
$\frac{nk}{2}$ edges, $2|n \vee 2|k.$ However, beyond
this, I am having few insights. I am wondering, how might I best
represent pairwise nonadjacent vertices using this knowledge of
the number of edges in this graph?
 A: I'm assuming that the word then is missing after $k\ge 1$. Suppose that $G$ is a counterexample: $G$ has $n$ vertices and $\frac{nk}2$ edges, and $i(G)<\frac{n}{k+1}$. Let $V_1$ be a maximal independent set of vertices in $G$, $V_2$ a maximal independent set of vertices in $G-V_1$, and so on through $V_m$ for some $m\in\Bbb Z^+$. Note that $m>k+1$; why?
Clearly $|V_j|<\frac{n}{k+1}$ for $j=1,\ldots,m$. Moreover, the maximality of each $V_j$ ensures that if $1\le j<\ell\le m$, and $v\in V_\ell$, then there is at least one edge between $v$ and some vertex in $V_j$.
There are $n-|V_1|>n-\frac{n}{k+1}=\frac{kn}{k+1}$ vertices in $\bigcup_{j=2}^mV_j$, each of which is connected by an edge to a vertex in $V_1$; this accounts for more than $\frac{ kn}{k+1}$ edges of $G$.  Similarly, there are more than $\frac{(k-1)n}{k+1}$ vertices in $\bigcup_{j=3}^mV_j$, each of which is connected by an edge to a vertex in $V_2$; this accounts for more than another $\frac{(k-1)n}{k+1}$ edges of $G$. 
Continuing in this fashion, we find that $G$ has more than
$$\sum_{j=1}^k\frac{jn}{k+1}=\frac{n}{k+1}\sum_{j=1}^kj$$
edges; can you see why this is a contradiction?
A: If you are allowed to use Turan's theorem, a simpler solution is possible.
$\overline G$ has $e=\binom n2-\frac{nk}2=\frac n2(n-1-k)$ edges.
Now $i(G)\geq\frac n{k+1}$ $\iff$ $\overline G$ has a clique of size at least $\frac n{k+1}$.
From Turan we know that avoiding a clique of size $r+1$ requires $e\leq(1-\frac1r)\frac{n^2}2$.
So we solve $\frac n2(n-1-k)\leq(1-\frac1r)\frac{n^2}2$, which is equivalent to $r\geq\frac n{k+1}$.
So (with $r=\lceil \frac n{k+1}\rceil-1$), avoiding a clique of size $\lceil \frac n{k+1}\rceil$ requires $r\geq\frac n{k+1}$.
Since this is impossible a clique of size $\lceil \frac n{k+1}\rceil$ must exist in $\overline G$, so an independent set of that size must exist in $G$.
