## Abstract

For a graph *G* with vertex set *V* (*G*) and independence number *α*(*G*), Selkow [*A Probabilistic lower bound on the independence number of graphs*, Discrete Math. 132 (1994) 363–365] established the famous lower bound *α* (*G*), where *N*(*v*) and *d*(*v*) = |*N*(*v*)| denote the neighborhood and the degree of a vertex *v* ∈ *V* (*G*), respectively. However, Selkow’s original proof of this result is incorrect. We give a new probabilistic proof of Selkow’s bound here.