Maximal independent set Created 2026-10-20 Updated 2026-11-05
A maximal independent set is an independent set that cannot be enlarged by adding another vertex. Equivalently, every vertex outside it has a neighbor inside it. This is maximality by inclusion, rather than maximum possible size.
In a three-vertex path, the middle vertex alone is a maximal independent set, as is the set containing both endpoints. Only the latter is a maximum independent set. A greedy procedure that repeatedly chooses a vertex and excludes its neighbors finds a maximal independent set, but can miss a maximum one. The distinction is important in approximation and scheduling algorithms.
Maximum independent set Created 2026-10-31 Updated 2026-11-05
An independent set with the largest possible cardinality in the given finite graph. Its size is the independence number. This differs from a maximal independent set, which only cannot be enlarged by adding vertices: another independent set can still be larger.