Properties
Relationship to other graph parameters
A set is independent if and only if it is a clique in the graph’s complement, so the two concepts are complementary. In fact, sufficiently large graphs with no large cliques have large independent sets, a theme that is explored in Ramsey theory.
A set is independent if and only if its complement is a vertex cover.^{[3]} Therefore, the sum of the size of the largest independent set $\alpha (G)$ and the size of a minimum vertex cover $\beta (G)$ is equal to the number of vertices in the graph.
A vertex coloring of a graph $G$ corresponds to a partition of its vertex set into independent subsets. Hence the minimal number of colors needed in a vertex coloring, the chromatic number $\chi (G)$, is at least the quotient of the number of vertices in $G$ and the independent number $\alpha (G)$.
In a bipartite graph with no isolated vertices, the number of vertices in a maximum independent set equals the number of edges in a minimum edge covering; this is Kőnig's theorem.
Maximal independent set
An independent set that is not a proper subset of another independent set is called maximal. Such sets are dominating sets. Every graph contains at most 3^{n/3} maximal independent sets,^{[4]} but many graphs have far fewer.
The number of maximal independent sets in n-vertex cycle graphs is given by the Perrin numbers, and the number of maximal independent sets in n-vertex path graphs is given by the Padovan sequence.^{[5]} Therefore, both numbers are proportional to powers of 1.324718..., the plastic number.