An independent vertex set of a graph G is a subset of the vertices such that no two vertices in the subset represent an edge of G. The figure above shows independent sets consisting of two subsets for a number of graphs (the wheel graph W_8, utility graph K_(3, 3), Petersen graph, and Frucht graph). Any independent vertex set is an irredundant set (Burger et al. 1997, Mynhardt and Roux 2020). The polynomial whose coefficients give the number of independent vertex sets of each cardinality in a graph G is known as its independence polynomial.

clique | disjoint sets | edge cover | empty set | independence number | independence polynomial | independent set | maximal independent vertex set | maximum independent edge set | maximum independent vertex set | Venn diagram | vertex cover