Past exam of the mathematics course of the University of Cambridge / 2025 / ii / Paper 3 / 17F / c

For each crossing pair, delete one of its two edges. At most $t(G)$ distinct edges are deleted, and the graph left behind has a crossing-free drawing. The planar graph edge bound therefore givessoThis is the linear estimate underlying the crossing lemma.

Choose each vertex independently with probabilityand take the induced drawing. Let its numbers of vertices, edges, and crossing pairs be $N,E,T$. Since crossing edges have four distinct endpoints,Part (i), with the harmless positive constant dropped, gives $T\ge E-3N$ for every outcome. Taking expectations,For $p=4n/e$, the right side is $4n^2/e$. Dividing by $p^4=256n^4/e^4$ proves the crossing lemma estimate