Proving Stable Set Size in Graphs with Average Degree d

[Dragonfall]

Homework Statement

Show using a probabilistic method that a graph with average degree d has a stable set of cardinality at least n/(2d).

I can't think of a probabilistic method that will do this.

 

[matt grime]

What is a stable set?

Work out the expected number of stable sets, I suppose - if all stable sets were of size less than n/2d, then that might be a bound on the expectation - show the bound is exceeded.

But that is just a guess as to the style of how probabilistic graph theory works - I've never answered a question on it and read precisely on paragraph about it once, so don't trust me.