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?



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$.

  • $\begingroup$ Can you please provide more details? And "has a set" and "every maximal" is different, no? $\endgroup$ – Eugene Aug 8 '17 at 20:01
  • $\begingroup$ 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. $\endgroup$ – Louis Aug 8 '17 at 20:55
  • $\begingroup$ 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 ? $\endgroup$ – Eugene Aug 8 '17 at 21:57
  • $\begingroup$ Yes. That's right. $\endgroup$ – Louis Aug 8 '17 at 22:16

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.