I am trying to prove above statement, but not sure where to start. I know that independence number and vertex cover number add up to n, and we have lower bound $ n/(\Delta+1) $ on the vertex cover number. I have tried induction, but don't know what to do when G is not bipartite. Any help will be appreciated. Thank you!
Edit: $\alpha (G) $ is independence number and $\Delta $ is the maximum degree.
On
Suppose $G$ is $k$-regular. Then $G$ has $\frac{kn}{2}$ edges.
Now find a maximum independent vertex set $A$, which by definition has $|A|=\alpha(G)$. Every edge associated with any vertex in $A$ is not shared with any other vertex in the set, so there are $k|A|$ distinct edges associated with $A$. Naturally $k|A| \le \frac{kn}{2}$ giving the result, provided only that $k>0$ (i.e. that $G$ has some edges).
Let $S$ be a set with more than $\frac{n}{2}$ vertices. Suppose that $S$ is independent. Then there would be $k|S|$ edges in $G$ incident to a vertex in $S$ (check to make sure you see why). This is more than $\frac{kn}{2}$ though, which is the total number of edges $G$ has (check to make sure you see why).
This is your answer.