Probabilistic probability problem for a graph Let G be a graph with $n$ vertices. Show that there exist an anti-clique with $x$ vertices, where. $x=\lceil \sum_{i=1}^n \frac{1}{d(v_i)+1} \rceil$, and $d(v_i)$ is the degree of vertex $i$ 
My work: see picture. Any hint would be appreciated!
 A: You are considering a fixed graph $G$.
So there is no interesting "probability that $v_1, v_2, \dots, v_k$ form an anti-clique": we can look in $G$ and see if they do or they don't, and then that probability is either $0$ or $1$.
Before you can talk about probabilities and expected values, you should choose something randomly.

This problem is actually fairly tricky, because the thing to choose randomly is not obvious. So here is your hint: the probability space.
Start with $S = \varnothing$. Then go through the vertices of $G$ in a uniformly random order. (That is, choose one of the $n!$ permutations of $V(G)$ uniformly at random, if $|V(G)|=n$, and consider vertices in the order they appear in that permutation.) For each vertex you consider, add it to $S$ if none of its neighbors are already in $S$.
You should now prove that the expected value of $|S|$ is at least $$\sum_{i=1}^n\frac1{\deg(v_i)+1}.$$ If so, then it must be somehow possible for $S$ to have size at least the ceiling of that bound.
