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.
Three examples of independent sets are , and : none contains both endpoints of an edge. The maximum independent sets are
The triangle on contributes at most one vertex, and the path on contributes at most two, giving the upper bound three. Both displayed sets attain it. A three-element choice cannot use , since that excludes and leaves at most one of the adjacent vertices . Consequently it must use or , together with both ; these are the only two choices. In particular, the maximum independent set is not unique.
Highlighted vertices give the two possible optimal choices. The third side of the left triangle rules out choosing both and .