Maximal independent set
![The graph of the cube has six different maximal independent sets, shown as the red vertices.](/Images/godic/202501/26/Cube-maximal-independence.svg4517.png")
![Two independent sets for the star graph show how vastly different in size two maximal independent sets (the right being maximum) can be.](/Images/godic/202501/26/Mis_stargraph_s84517.png")
![](/Images/godic/202501/26/Mis_related_sets4517.png")
In graph theory, a maximal independent set (MIS) or maximal stable set is an independent set that is not a subset of any other independent set. In other words, there is no vertex outside the independent set that may join it because it is maximal with respect to the independent set property.