# About independent set in triangle free graphs

From Wikipedia :

An independent set of $\sqrt{n}$ vertices in an $n$-vertex triangle-free graph is easy to find: either there is a vertex with more than $\sqrt{n}$ neighbors (in which case those neighbors are an independent set) or all vertices have less than $\sqrt{n}$ neighbors (in which case any maximal independent set must have at least $\sqrt{n}$ vertices)

Why does any maximal stable set have at least square root of $n$ vertices?

Thanks.

The point is that the graph is triangle free, so if $j$ and $k$ are both neighbours of $i$, then the edge $\{j,k\}$ is not in the graph. This means that $N_i = \{j : \text{$i$is a neighbour of$j$}\}$ is an independent set for any $i$.
The other fact being used is that a graph with $n$ vertices of maximum degree $\Delta$ has an independent set of size at least $\lfloor n/(\Delta+1)\rfloor$.
• If the maximum degree is $\Delta$ than any independent set of size $t$ has at most $t\Delta$ neighbours. Unless $t(\Delta +1) \ge n$, it's not maximal. – Louis Aug 8 '17 at 20:55
• Okay, so if maximum degree is less than $\sqrt{n}$, then we have the bound. so here the triangle free property isn't used right? It is used only when saying that if a vertex has big neighborhood then take it as independent set. Am I right ? – Eugene Aug 8 '17 at 21:57