Caro-Wei bound
= Caro-Wei bound
{c}
{title2=$\alpha(G)\geq\sum_v\frac1{1+\deg v}$}
For a finite simple <graph>, $\alpha(G)\geq\sum_{v\in V(G)}1/(1+\deg v)\geq |V(G)|^2/(|V(G)|+2|E(G)|)$. Randomly order its <vertices> and retain each <vertex> preceding all its <graph neighbours>. This gives an <independent set> with the first expression as its <expected value>. The second inequality is the <Cauchy-Schwarz inequality>.