= Independent set
{disambiguate=graph theory}
{wiki}
= Independent set
{synonym}
An <independent set> selects mutually compatible objects when an <edge> of a <graph> represents a conflict. For example, if <vertices> are activities and <edges> join activities that cannot occur together, an <independent set> is a collection that can share one time slot. Finding the largest such collection is measured by the <independence number>.https://introtcs.org/public/lec_12_NP.html[Barak, Introduction to Theoretical Computer Science, Chapter 14, The independent set problem]{ref}
In a finite <simple graph> $G=(V,E)$, an <independent set> is a <subset> $I\subseteq V$ with no <edge> joining two selected <vertices>:
$$
u,v\in I,\ u\ne v\Longrightarrow\{u,v\}\notin E.
$$
The empty <set> and every singleton <set> are <independent sets>. In the <cycle graph> $C_5$ drawn under <vertex cover>, $\{0,2\}$ is an <independent set>, but $\{0,4\}$ is not: the closing <edge> $40$ joins those two <vertices>. Choosing nonconsecutive labels is insufficient unless the wraparound <edge> is checked.
An <independent set> of maximum size has <cardinality> equal to the <independence number>. Being unable to add another <vertex> only makes an <independent set> inclusion-maximal. In the <star graph> $K_{1,3}$, the centre alone is inclusion-maximal, since it is adjacent to every leaf, but the three leaves form a larger <independent set>. This distinction mirrors the difference between an inclusion-minimal <vertex cover> and a <minimum vertex cover>.
Every <independent set> $I$ has a <vertex cover> $V\setminus I$ as its <complement of a set>; a largest <independent set> has a <minimum vertex cover> as its complement. In every <proper vertex colouring>, each <colour class> is an <independent set>, so <graph coloring> partitions the <vertices> into mutually compatible groups.
Back to article page
