Probabilistic probability problem for a graph

Question

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!

Answer 1

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.