40 kids play 80 chess games. Prove that there are at least $8$ kids that did not play with each other.
In graph terms: if there are $40$ vertices and $80$ edges, prove that there is an independent set of size $\geq 8$.
I was shown a probabilistic solution and forgot it: they proved that there is an anti-clique of size at least $\displaystyle\sum_{v \in V} \frac{1}{\deg(v)+1}$, and then the result follows from the GM-HM inequality by $\displaystyle\frac{|V|}{\sum\limits_{v \in V} \frac{1}{\deg(v)+1}}\leq \frac{\sum\limits_{v \in V} ({\deg(v)+1})}{|V|} $, from which by plugging in the values we get $\displaystyle\frac{40}{\sum\limits_{v \in V} \frac{1}{\deg(v)+1}}\leq \frac{ 2|E|+40 }{40} \implies \sum_{v \in V} \frac{1}{\deg(v)+1}\geq \frac{40^2}{160+40}=8. \; \square$
The $\dfrac{1}{\deg(v)+1}$ looks like the probability of choosing the node itself from among it and its neighbors, but a process of choosing probabilistically a neighbor for each vertex seems inconsistent (due to symmetry) and irrelevant.
Let's form an independent set of vertices by doing the following. First, randomly permute the vertices $v_1,\ldots,v_n$. Initialize $S = \{\}$. Then for $k = 1,2,3,\ldots,n$ if $v_k$ is still in the graph, add it to $S$ and delete $v_i$ and each of its neighbors from the graph. Then, $S$ is an independent set.
Define a random variable $I_v = 1$ if $v \in S$ and $I_v = 0$ if $v_k \not\in S$. Then, $|S| = \displaystyle\sum_{v \in V}I_v$.
For each vertex, $v \in S$ if $v$ has a lower index than each of its neighbors. If $v$ has $d(v)$ neighbors, then the probability of $v$ having the lowest index among itself and its neighbors is $\dfrac{1}{d(v)+1}$.
Hence, $\mathbb{E}[I_v] = \Pr[I_v = 1] = \dfrac{1}{d(v)+1}$. So, by linearity $\mathbb{E}[|S|] = \displaystyle\sum_{v \in V}\dfrac{1}{d(v)+1}$.
Therefore there must be at least one permutation of the vertices for which the above algorithm gives us an independent set of size at least $\displaystyle\sum_{v \in V}\dfrac{1}{d(v)+1}$.