Improving the Caro-Wei bound and applications to Turán stability

We prove that if $G$ is a graph and $f(v)\le 1\mathrm{/}(d(v)+1\mathrm{/}2)$ for each $v\in V(G)$, then either $G$ has an independent set of size at least ${\sum }_{v\in V(G)}f(v)$ or $G$ contains a clique $K$ such that ${\sum }_{v\in K}f(v)>1$. This result implies that for any $\sigma \le 1\mathrm{/}2$, if $G$ is a graph and every clique $K\subseteq V(G)$ has at most $(1-\sigma )(\mathrm{\mid }K\mathrm{\mid }-\sigma )$ simplicial vertices, then $\alpha (G)\ge {\sum }_{v\in V(G)}1\mathrm{/}(d(v)+1-\sigma )$. Letting $\sigma =0$ implies the famous Caro-Wei Theorem, and letting $\sigma =1\mathrm{/}2$ implies that if fewer than half of the vertices in each clique of $G$ are simplicial, then $\alpha (G)\ge {\sum }_{v\in V(G)}1\mathrm{/}(d(v)+1\mathrm{/}2)$, which is tight for the 5-cycle. When applied to the complement of a graph, this result implies the following new Tur' an stability result. If $G$ is a $K_{r+1}$-free graph with more than $(1-1\mathrm{/}r)n^2\mathrm{/}2-n\mathrm{/}4$ edges, then $G$ contains an independent set $I$ such that at least half of the vertices in $I$ are complete to $G-I$. Applying this stability result iteratively provides a new proof of the stability version of Tur' an’s Theorem in which $K_{r+1}$-free graphs with close to the extremal number of edges are $r$-partite.