A graph with an average degree of d contains a stable set of cardinality at least n/(2d). This conclusion is derived using probabilistic methods, specifically by calculating the expected number of stable sets. If all stable sets were smaller than n/(2d), the expectation would be bounded, which contradicts the established result. This analysis confirms the existence of larger stable sets in graphs with average degree d.
PREREQUISITESMathematicians, computer scientists, and students studying graph theory or combinatorial optimization, particularly those interested in probabilistic methods and their applications in proving theoretical results.