# 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)<\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.

• Sorry also in the turan's theorem , they mentioned $K_{r-1}$free graph.What is a $k_n$free graph ? – nafhgood Nov 28 '18 at 17:01
• @mathnoob An $H$-free graph means that it doesn't have a subgraph isomorphic to $H$. – Juho Nov 28 '18 at 17:03