Independent Set

Definition

Independent Set

Let $G=(V,E)$ be a finite undirected graph. An independent set is a subset $I\subseteq V$ containing no two adjacent vertices:

$$I\text{ is independent in }G⟺\forall u,v\in I:u\ne v⟹\{u,v\}\notin E.$$

Equivalently, the induced subgraph $G[I]$ has no edges. The vertices in $I$ may therefore coexist without any edge joining two of them.

Complement Characterisation

Independent Set–Vertex Cover Complement

Let $G=(V,E)$ be a graph, let $I\subseteq V$, and let $C=V\setminus I$. Then $I$ is independent in $G$ if and only if $C$ is a vertex cover of $G$:

$$I\text{ is independent in }G⟺C\text{ is a vertex cover of }G.$$