I've seen this question being asked on here before but I haven't been able to solve this problem with the provided answers. If it is of any use I've been able to prove that $G$ has an independent set $S:|S|= \lfloor \sqrt{n} \rfloor$ but I don't really know what I can do with this. How can I go about proving this? I'm only looking for some ideas, not a full proof.
Edit: As you can see in the conversation below a person was kind enough to try to help me but I didn't get anywhere. Are there any further tips that can be given such that I can prove this theorem without actually giving away all of it? Thus far I've been unable to solve this problem and thus far all other students in my class have failed as well.
An independent set of size $\sqrt n$ is not really the best we can do. Rather, we can show that in any graph on $\binom{k+1}{2}$ (rather than $k^2$) vertices, there is either a triangle or an independent set of size $k$ - this is a special case of Ramsey's theorem, but you can also try to prove this independently if you like.
Even this bound is not best possible, but better results are hard to prove.
This argument gives us an independent set of size $\sqrt{2n}$ in the limit as $n \to \infty$, so intuitively, we should be able to prove a bound on the chromatic number of about $\sqrt{2n}$ as well. Try doing this in the same way as you did before; even if you get another pesky $+1$ at the end, it shouldn't stop you, because $\sqrt{2n}$ is better than $2\sqrt n$.