# 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?

• Suppose your graph has $n$ vertices, and suppose each vertex has degree at most $t-1.$ Let $S$ be a maximal independent set, of size $s.$ Can you show that $n\le st?$ – bof Aug 16 '17 at 23:36