---
tag: 0KZJ82WEPP
kind: definition
name: Independent set
msc: [05C69]
defines: 08ANQHHG3P
sources:
  - url: https://en.wikipedia.org/wiki/Independent_set_(graph_theory)
    locator: lead section
---

## Definition

Let $G$ be a [[graph|0JD5C82QMB]].
An independent set in $G$ is a set $S$ of vertices of $G$ such that no two vertices of $S$ are adjacent.

## Remarks

A set is independent in $G$ if and only if it is a [[clique|0G52BPNPKG]] in the [[complement graph|0RNMP6VCR2]].
A set $S$ is independent if and only if its complement in the vertex set is a [[vertex cover|0KDADE9RQ8]].
The largest size of an independent set is the independence number $\alpha(G)$. Each colour class of a [[colouring|0874138YP6]] is an independent set.

## Explanations

### L1 human

An independent set is a set of vertices with no edge between any two of them.
In a conflict graph, it is a set of tasks that can all happen at the same time.