proof of crossing lemma

Euler’s formula implies the linear lower bound $\\operatorname{cr}(G)\\geq m-3n+6$ , and so it cannot be used directly. What we need is to consider the subgraphs of our graph, apply Euler’s formula on them, and then combine the estimates. The probabilistic method provides a natural way to do that.

Consider a minimal embedding of $G$ . Choose independently every vertex of $G$ with probability $p$ . Let $G_{p}$ be a graph induced by those vertices. By Euler’s formula, $\\operatorname{cr}(G_{p})-m_{p}+3n_{p}\\geq 0$ . The expectation is clearly

E(\\operatorname{cr}(G_{p})-m_{p}+3n_{p})\\geq 0.

Since $E(n_{p})=pn$ , $E(m_{p})=p^{2}m$ and $E(X_{p})=p^{4}\\operatorname{cr}(G)$ , we get an inequality that bounds the crossing number of $G$ from below,

\\operatorname{cr}(G)\\geq p^{-2}m-3p^{-3}n.

Now set $p=\\frac{4n}{m}$ (which is at most $1$ since $m\\geq 4n$ ), and the inequaliy becomes

\\operatorname{cr}(G)\\geq\\frac{1}{64}\\frac{m^{3}}{n^{2}}.

Similarly, if $m\\geq\\frac{9}{2}n$ , then we can set $p=\\frac{9n}{2m}$ to get

\\operatorname{cr}(G)\\geq\\frac{4}{243}\\frac{m^{3}}{n^{2}}.

References

1 Martin Aigner and Günter M. Ziegler. Proofs from THE BOOK. Springer, 1999.