# Independent set ¶

Go back

In French, we are mainly using the keywords Stable and Stabilité. The independence set, also called stable set/ensemble stable is a set $S$ in which we can't find two adjacent vertices.

• maximal independent set: not stable anymore if we add a vertex
• maximum independent set:
• we can't make a set with more vertices
• $\alpha (G) = Card(\text{maximum_stable_set})$
• let $h$ be the highest degree

@ |\text{maximum_stable_set}| \ge \lceil \frac{n}{h+1} \rceil @