---
tag: 34B1PW5EE2
kind: statement
role: theorem
name: Crossing number inequality
msc: [05C10, 52C10, 05C62]
uses: [00C0BR7D7H, SWJZ4QRF9W, 0SM1REAVYJ, 3B55HNS754]
about: [SWJZ4QRF9W]
sources:
  - url: https://en.wikipedia.org/wiki/Crossing_number_inequality
same_as:
  wikidata: Q24896206
  wikipedia: Crossing number inequality
---

## Statement

Let $G$ be a finite simple [[graph|00C0BR7D7H]] with $n$ vertices and $e$ edges, and let $\operatorname{cr}(G)$ be its [[crossing number|SWJZ4QRF9W]].
If $e \ge 4n$, then
$$\operatorname{cr}(G) \ge \frac{e^3}{64 n^2}.$$

## Remarks

A planar simple graph with $n \ge 3$ vertices has at most $3n - 6$ edges by the [[edge bound for planar graphs|0SM1REAVYJ]].
Removing one edge per crossing from a drawing gives a planar graph, so $\operatorname{cr}(G) \ge e - 3n$ for every simple graph.
Now keep each vertex of an optimal drawing independently with probability $p$, as in the [[probabilistic method|3B55HNS754]].
Taking expectations in the weak bound gives $p^4 \operatorname{cr}(G) \ge p^2 e - 3pn$, and the choice $p = 4n/e$ gives the result.
Example: the complete graph $K_n$ has $e = n(n-1)/2$ edges, which is at least $4n$ for $n \ge 9$, so $\operatorname{cr}(K_n) \ge c n^4$ for a constant $c > 0$.
Without a hypothesis like $e \ge 4n$ the bound fails: a graph with $e = n$ edges can be a cycle, which has crossing number $0$.

## Explanations

### L1 human

When a graph has many more edges than vertices, any drawing of it in the plane must have many crossings.
The inequality says how many: at least a constant times $e^3 / n^2$.
Doubling the number of edges, with the same vertices, forces about eight times as many crossings.

### L2 human

The inequality was proved by Ajtai, Chvátal, Newborn and Szemerédi and, independently, by Leighton, in the early 1980s.
Its main use in discrete geometry is through incidence bounds.
László Székely used it to give short proofs of the [[Szemerédi–Trotter theorem|NQBWFSC1E0]] on point-line incidences and of the $O(n^{4/3})$ bound in the [[unit distance problem|EPWB2JEXPE]].
One draws the points as vertices and the pieces of lines or circles as edges, and compares the forced crossings with the number of pairs of curves.