# Given all maximal independent sets of a graph, find the maximum indepdent set

I am new to this independent set problem in graph theory. As per my understanding so far an independent set is a set of vertices in which no two vertices are adjacent. And the maximal independent set is a set of vertices in which if some vertex is added it will construct an edge.

I understand this now my question is if given all maximal independent set for a graph then the maximum independent set of that graph will be maximal independent set with maximum cardinality right?

Note: As per my understanding there can be more than one maximum independent set but their cardinality will be same.

• Your understanding is correct. Commented Jun 23, 2018 at 18:13

If an independent set is maximal, it means you cannot add any more vertices into the set. As you correctly suggest, this does not mean that the set is necessarily a maximum independent set in the graph.

You are also correct in saying that every maximum independent set is maximal, and that a graph can have several maximum independent sets.