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.

Improve this question
$\endgroup$
1
  • 1
    $\begingroup$ Your understanding is correct. $\endgroup$
    – Yuval Filmus
    Jun 23, 2018 at 18:13

1 Answer 1

Reset to default
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.

Improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

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