proof of crossing lemma
Euler’s formula implies the linear lower bound , 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.
Since , and , we get an inequality that bounds the crossing number of from below,
Now set (which is at most since ), and the inequaliy becomes
Similarly, if , then we can set to get
- 1 Martin Aigner and Günter M. Ziegler. Proofs from THE BOOK. Springer, 1999.
|Title||proof of crossing lemma|
|Date of creation||2013-03-22 13:38:46|
|Last modified on||2013-03-22 13:38:46|
|Last modified by||bbukh (348)|