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

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].

[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 & Sons, 2004.

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

There are several non-probabilisitc proofs : 1/ using greedy algorithm deleting minimum degree : See : https://www.sciencedirect.com/science/article/pii/S0166218X13001339 https://onlinelibrary.wiley.com/doi/10.1002/jgt.3190150110

2/ deleting vertices of maximum degree : see :https://www.combinatorics.org/ojs/index.php/eljc/article/view/v20i1p33

There are everal more variations.

My original 1999 proof was via induction and deleting vertex of maximum degree.

Induction on the order of G . True for |G| = 1. Assume for |G| = n let prove it for |G| = n +1. Choose a vertex v of minimum degree . Consider H = G - N[v]. Clearly a(G)> = 1 + a(H) > = 1 + sum { 1/( deg_H(u) +1) :u in V(H)} > = ** sum { 1/(deg_G(w)) +1 ) :w in N[{v] } + sum { 1/( deg_H(u) +1) : u in V(H)} = sum { 1/(deg_G(w)) +1 ) : w in N[{v] } + sum { 1/( deg_G(u) +1 : u in V(G)\N[v]}= sum { 1/(deg(w)+1 ) w in V(G) }. deg_G(w) the degree of w in G , deg_H(u) the degree of u in H. ** observe 1=sum {1/(deg(v)+1 ):w in N[v] } > = sum{ 1/(deg_G(w) +1) : w in N[v] } as v has minimum degree . Best - Yair Caro .