Independent set (graph theory)

In graph theory, an independent set, stable set, coclique or anticlique is a set of vertices in a graph, no two of which are adjacent. That is, it is a set S {\displaystyle S} of vertices such that for every two vertices in S {\displaystyle S} , there is no edge connecting the two.