Past exam of the graph Theory and Probabilistic Combinatorics course of the University of Oxford / 2009 / B / 6 / a / ii / Solution

The asymmetric Lovász local lemma states that if there are numbers $0\le x_i<1$ withfor every index, thenFor maximum out-degree $d\ge 1$, take every $x_i=1/(d+1)$. Sinceone has $x_i(1-x_i{)}^d\ge 1/[e(d+1)]\ge p$. Fewer than $d$ outgoing neighbours only increases the product, so the hypothesis is satisfied whenever $ep(d+1)\le 1$.

If $d=0$, take $x_i=p<1$; the neighbour products are empty and equal one. This separately covers the case in which $1/(d+1)$ would equal the forbidden value one. Thus the symmetric local lemma follows in every case.