Under "more information", in the
MaximalIndependentVertexSet description (part of GraphUtilities) it says this function "gives an (approximate) maximal set of vertices such that no two vertices form an edge."
In what sense is it "approximate" ? I understand that finding a
maximum independent set is hard, and one may want to approximate with a
maximal set. But if I just want some maximal set, that should be easy to find without approximation.
In brief, how could the output of MaximalIndependentVertexSet fail to be a proper maximal independent set?