0
$\begingroup$

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.

$\endgroup$
  • 1
    $\begingroup$ Your understanding is correct. $\endgroup$ – Yuval Filmus Jun 23 '18 at 18:13
2
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.