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

Table of contents
- Solution i

Solution

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 gives

e - t (G) \leq 3 n - 6,

so

t (G) \geq e - 3 n + 6 .

This is the linear estimate underlying the crossing lemma.

 Ancestors (11)

 View article source

 Discussion (0)

There are no discussions about this article yet.

 Articles by others on the same topic (0)

There are currently no matching articles.

  See all articles in the same topic Create my own version