proof of crossing lemma

Euler’s formula implies the linear lower bound cr(G)m-3n+6, and so it cannot be used directly. What we need is to consider the subgraphsMathworldPlanetmath 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 Gp be a graph induced by those vertices. By Euler’s formula, cr(Gp)-mp+3np0. The expectation is clearly


Since E(np)=pn, E(mp)=p2m and E(Xp)=p4cr(G), we get an inequality that bounds the crossing number of G from below,


Now set p=4nm (which is at most 1 since m4n), and the inequaliy becomes


Similarly, if m92n, then we can set p=9n2m to get



  • 1 Martin Aigner and Günter M. Ziegler. Proofs from THE BOOK. Springer, 1999.
Title proof of crossing lemma
Canonical name ProofOfCrossingLemma
Date of creation 2013-03-22 13:38:46
Last modified on 2013-03-22 13:38:46
Owner bbukh (348)
Last modified by bbukh (348)
Numerical id 6
Author bbukh (348)
Entry type Proof
Classification msc 05C10
Classification msc 05C80
Related topic ProbabilisticMethod