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.

Articles by others on the same topic (1)

A **maximal independent set** (MIS) is a specific concept within graph theory. To understand an MIS, it's important to first grasp the definitions of an independent set and what it means for that set to be maximal. 1. **Independent Set**: In a graph, an independent set is a subset of vertices such that no two vertices in the subset are adjacent. This means that there are no edges connecting any pair of vertices in the independent set.