Past exam of the mathematics course of the University of Cambridge / 2021 / iii / Paper 161 / 1 / i / Solution

Let $X$ be the number of crossings in the drawing, placed in general position. Deleting at most one edge at each crossing leaves a planar graph, so the Euler formula for a connected planar graph gives

Now retain every vertex independently with probability $p$, together with every edge whose endpoints survive. The expected numbers of retained vertices, edges and crossings are $pn,p^{2}m,p^{4}X$. Applying the preceding inequality to each sampled drawing and taking expectations givesBecause $m\ge 6n$, choose $p=6n/m\le 1$. Thenand thereforeThus the Crossing lemma holds here with the absolute constant $c=1/72$.