Alternate proof of the Caro-Wei theorem for lower bounding the independence number Let $G$ be a graph on $n$ vertices whose degree sequence is $d_1,d_2,...,d_n$. Let $\alpha(G)$ denote the size of maximum independent set of $G$, i.e., the size of a maximum subset of vertices of $G$ that are pairwise non-adjacent. So Caro-Wei says that $\alpha(G) \geq \sum_{d_i \in V(G)}{\frac{1}{1+d_i}}$. The standard probabilistic proof goes as follow, here we let $V(G)=\{1,2,...,n\}$:

Consider the set $S_n$ of permutations of the vertices in $G$ and $\sigma \in S_n$ be a permutation in $S_n$. Let $A_i$ be the event that $\sigma(i)&lt;\sigma(j), \forall j \in N(i)$ namely all neighbours $j$ of the vertex $i$ gets maps to by $\sigma$ to some number greater than $\sigma(i)$. There are $\binom{n}{1+d_i}$ places that $\sigma$ can map the vertex $i$ and its neighbors to. Futhermore, $\sigma(i)$ is the smallest, so there are $d_i!$ ways for the neighbours of  $i$ to be map to and $(n-d_i-1)!$ ways for the remaining number to be permuted. So $P(A_i)=\frac{\binom{n}{d_i+1} d_i!(n-d_i-1)!}{n!}=\frac{1}{1+d_i}$. Now consider the subset of the vertex set of $G$, $U=\{i \mid A_i = \text{true}\}$. Notice that two vertices in $U$ does not share an edge. The expected value $E[|U|]=\sum_{i\in \{1,...,n\}}{\frac{1}{1+d_i}}$. So done.

But I'm wondering if there is a proof not involving probabilistic method.
An algorithmic proof is given by Murphy [1, Section 1], where he attributes the algorithm to Erdös [2].

As a side remark, I don't know what the original proof of Caro or Wei is, but I believe the proof you mention is due to Alon and Spencer [3].



[1] Murphy, Owen. "Lower bounds on the stability number of graphs computed in terms of degrees." Discrete Mathematics 90.2 (1991): 207-211.

[2] Erdös, Paul. "On the graph theorem of Turán." Mat. Lapok 21. (1970): 249-251.

[3] Alon, Noga, and Joel H. Spencer. The Probabilistic Method. John Wiley &amp; Sons, 2004.