= 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
$$
m-X\leq3n,
\qquad\text{hence}\qquad X\geq m-3n.
$$
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^2m,p^4X$. Applying the preceding inequality to each sampled drawing and taking expectations gives
$$
p^4X\geq p^2m-3pn.
$$
Because $m\geq6n$, choose $p=6n/m\leq1$. Then
$$
p^2m-3pn=\frac{18n^2}{m},
$$
and therefore
$$
X\geq\frac{18n^2/m}{(6n/m)^4}
=\frac1{72}\frac{m^3}{n^2}.
$$
Thus the <Crossing lemma> holds here with the absolute constant $c=1/72$.
Back to article page
