How to prove that triangle-free graph with $t^2$ vertices contains set of $t$ vertices that form an independent set Let $G$ be a triangle-free graph with $t^2$ vertices. Prove that $G$ contains a set of $t$ vertices that form an independent set. I don't know how to start this proof. Please help.
Observation: If $G$ has a vertex $v$ of degree at least $t$, then the neighbors of $v$ form an independent set of size $t$, since an edge within the neighborhood will create a triangle. So, then if it is not the case, every vertex has degree at most $t-1$. How do we construct an independent set?
 A: It's enough to show that any $n$-vertex triangle-free graph $G$ has an independent set of size at least $\sqrt{n}$.
Any graph $H$ (triangle-free or not) with $n$ vertices and maximum degree $\Delta=\Delta(H)$ has an independent set of size at least $\left\lceil n/(\Delta+1) \right\rceil$. Just consider the greedy algorithm in order to get a maximal independent set $I(H)$, which in each step search only in the non-neighborhood $\overline{N}(v)$ of a arbitrary first vertex $v$.
$$
\text{Choose } v\in V(H)\\
I(H)\leftarrow \{v\}\cup I(\overline{N}(v))
$$
Note that in each step the algorithm consider at most $\Delta+1$ vertices, therefore it needs to take at least  $\left\lceil n/(\Delta+1) \right\rceil$ steps to stop, i.e.,
$$
|I(H)|\geq \left\lceil n/(\Delta+1) \right\rceil.
$$
On the other hand, if $G$ is a $n$-vertex triangle-free graph, either there is a vertex with at least $\sqrt{n}$ neighbors, in which case those neighbors are an independent set, or $\Delta(G)\leq\sqrt{n}-1$, in which case any maximal independent set $I(G)$  has size at least $\left\lceil n/(\Delta+1) \right\rceil \geq \left\lceil n/\sqrt{n} \right\rceil \geq \sqrt{n}$.
