Quote Originally Posted by StainlessSteel View Post
I don't agree with the combinatorics, though, as:

If g is the number of vertices in the max-clique which can be members of the indep-set as well, we're ignoring the fact that there might be vertices in the independent set which might be members of the clique.
I don't think this case is possible since the clique is maximum:
Assume there is some vertex v in the IS which is connected to all vertices of the clique, it follows that degree(v) >= m and therefore it would have to be included in the clique on the first place.

Regards,
Zachm