Graph independence number (Caro-Wei) estimate without probabilistic argument?

Question

A short introduction: The independence number $\alpha(G)$ of a graph $G$ is the cardinality of the largest independent vertex set. Independent vertex set is made only of vertices with no edges between them.

For example, the set shown above has $\alpha(G)=3$ because in set $\{A,C,E\}$ all vertices are independent and it's impossible to construct a set with four independent elements.

I have stumbled upon a theorem of Caro and Wei who independently provided the following estimate for the lower bound:

$$\alpha(G)\ge\sum_{i=1}^{n}\frac1{d_i+1}\tag{1}$$

My naive attempts to prove the statement fell short so I started to look for a proof elsewhere. Despite the fact that this famous result of Caro and Wei was quoted in many places (Google returned thousands of pages on the first try), it was not easy to find a full proof. This one turned out be my personal favorite (copied from here):

All other proofs that I have found so far are more or less just a copy of it, most often with fewer words. Another copy can be found on MSE (please note that this post is not a copy of the same question).

The proof starts with some combinatorics and then jumps to probabilities and expectations. It's perfectly readable and I have enjoyed it immensely but...

Imagine that you have to explain the theorem to someone (like my son) who is very good at combinatorics but has zero experience with probabilities and expectations.

My question is: Is there a proof of (1) that is not based on a probabilistic argument? Can we replace the probabilistic part of the proof with something that is "more basic", if you understand what I mean. My attemts to find such proof were unsuccessful.

Answer 1

Can we replace the probabilistic part of the proof with something that is "more basic"?

Yes, it is a shame that it is never explained that no actual probability is being used in these types of proofs. Below, $\pi$ represents a permutation, $v$ represents a vertex, and $u \sim v$ means $(u,v) \in E$.

$\sum_\pi \sum_v \prod_{u \sim v} 1_{\pi(v) < \pi(u)} = \sum_v \sum_\pi \prod_{u \sim v} 1_{\pi(v) < \pi(u)} = \sum_v {n \choose d_v+1}d_v!(n-1-d_v)! = n!\sum_v\frac{1}{d_v+1}$, so by pigeonhole, there is some $\pi$ with $\sum_v \prod_{u \sim v} 1_{\pi(v) < \pi(u)} \ge \sum_v \frac{1}{d_v+1}$. Then the set of all $v$ with $\pi(v) < \pi(u)$ for all $u \sim v$ is an independent set of size at least $\sum_v \frac{1}{d_v+1}$.

Answer 2

Induction on the order of $G$. It's true for $|G| = 1$. Now assume it's true for $|G| \leq n$ and let's prove it for $|G| = n+1$.

Choose a vertex $v$ of minimum degree. Consider $H = G - N[v]$. Clearly $$ \begin{align*} \alpha(G) & \geq 1 + \alpha(H) \\ & \geq 1 + \sum_{u \in V(H)} \frac{1}{\mathrm{deg}_H(u)+1} \\ & \geq \sum_{w \in N[v]} \frac{1}{\mathrm{deg}_G(w)+1} + \sum_{u \in V(H)} \frac{1}{\mathrm{deg}_H(u)+1} \tag{*} \\ & = \sum_{w \in N[v]} \frac{1}{\mathrm{deg}_G(w)+1} + \sum_{u \in V(G) \setminus N[v]} \frac{1}{\mathrm{deg}_H(u)+1} \\ & \geq \sum_{w \in V(G)} \frac{1}{\mathrm{deg}_G(w)+1} \end{align*} $$ where $\mathrm{deg}_G(w)$ is the degree of $w$ in $G$ and $\mathrm{deg}_H(u)$ is the degree of $u$ in $H$.

To show $(^*)$, observe $$ 1 = \sum_{w \in N[v]} \frac{1}{\mathrm{deg}(v)+1} \geq \sum_{w \in N[v]} \frac{1}{\mathrm{deg}_G(w)+1} $$ since $v$ has minimum degree.