2
$\begingroup$

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.

Improve this question
$\endgroup$

1 Answer 1

Reset to default
2
$\begingroup$

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

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

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

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