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

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

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

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.