In graph theory, a maximal independent set is an independent set such that adding any other node to the set forces the set to contain an edge. Equivalently, an independent set W is maximal if every vertex outside of W is connected to some vertex in W. Also, an independent set W is maximal if whenever S is an independent set such that W \subset S, it follows that W = S.