From Planar Edge Bounds to Crossing Numbers
A graph can be drawn in the plane with crossings even when no crossing-free drawing exists. The crossing number measures the smallest number of crossings that any drawing can achieve. A planar edge bound gives a useful way to prove that this number must be large: if a graph has many more edges than a planar graph on the same vertices can have, some edges must cross. Random vertex sampling strengthens that observation into a cubic lower bound in the number of edges.
Throughout, graphs are finite and simple. A drawing places distinct points for the vertices and represents each edge by a simple arc between its endpoints. We consider drawings in general position: crossings are transverse intersections of edge interiors, no vertex lies in an edge interior, and no three edges cross at one point. The crossing number \(\operatorname{cr}(G)\) is the minimum number of crossings over all such drawings of \(G\).
We use the standard drawing convention that adjacent edges—edges sharing an endpoint—do not cross. This does not change the crossing number: if adjacent edges cross, their portions from the shared endpoint to a crossing can be interchanged locally. The crossing is removed, while intersections with other edges are merely reassigned between the two edges. Any resulting loops can be erased, and the drawing can then be perturbed into general position without increasing its number of crossings. Thus a minimum drawing can be chosen with no adjacent-edge crossings. In particular, the two edges at any crossing in this drawing have four distinct endpoints.
The planar edge bound applies even to a graph with isolated vertices or several components. We will use the weaker inequality \(e\le3v\) because it avoids separate terms in the sampling calculation.
Proof. For each crossing in the drawing, select one of the edges passing through it, and delete every selected edge (an edge selected more than once is deleted only once). At most \(X\) edges are deleted. Every crossing involved an edge that was deleted, so the remaining drawing has no crossings and is a drawing of a simple planar graph on the same vertex set. Its number of edges is at least \(|E(H)|-X\), and the planar edge bound says it is at most \(3|V(H)|\). Therefore \(|E(H)|-X\le3|V(H)|\), which rearranges to the claimed inequality. \(\square\)
The Crossing Lemma
The condition \(n\ge1\) matters: if the graph is empty, then \(m=n=0\), and the displayed fraction is undefined. The density condition \(m\ge4n\) ensures that the sampling probability used below is at most one.
Proof. Fix a minimum drawing of \(G\) in general position with no crossings between adjacent edges. Independently retain each vertex with probability \(p=4n/m\), and let \(H\) be the induced subgraph on the retained vertices. The assumption \(m\ge4n\) gives \(0<p\le1\), so this is a valid probability.
Let \(V_H=|V(H)|\), \(E_H=|E(H)|\), and let \(X_H\) be the number of crossings in the drawing inherited by \(H\). Each vertex is retained with probability \(p\), so \(\mathbb{E}[V_H]=pn\). Each edge is retained exactly when both its endpoints are retained, an event of probability \(p^2\); hence \(\mathbb{E}[E_H]=p^2m\). Each crossing in the fixed drawing has four distinct endpoints. It survives exactly when all four are retained, an event of probability \(p^4\). Summing over the \(\operatorname{cr}(G)\) crossings gives \(\mathbb{E}[X_H]=p^4\operatorname{cr}(G)\).
For every outcome of the sampling, the planarization bound gives \(X_H\ge E_H-3V_H\). Taking expectations preserves this inequality, so
Substitute \(p=4n/m\). The right-hand side becomes
Since \(p^4=256n^4/m^4\), division by this positive quantity yields
This proves the theorem. The argument depends on sampling an induced subgraph: vertices survive with probability \(p\), edges with probability \(p^2\), and crossings with probability \(p^4\). \(\square\)
Worked Applications
Worked Example: The Complete Graph \(K_{10}\)
Let \(G=K_{10}\), with \(V(G)=\{1,2,\ldots,10\}\) and \(E(G)=\{ij:1\le i<j\le10\}\). There are \(10\cdot9/2=45\) edges, so \(n=10\), \(m=45\), and \(45\ge4\cdot10=40\). The Crossing Lemma applies.
Its bound is
The crossing number is an integer. Since \(14\cdot256=3{,}584<3{,}645\) and \(15\cdot256=3{,}840>3{,}645\), the bound implies \(\operatorname{cr}(K_{10})\ge15\).
Check by sampling: Here \(p=4n/m=40/45=8/9\). The expected numbers of retained vertices and edges are \(10(8/9)=80/9\) and \(45(8/9)^2=45\cdot64/81=320/9\). Thus \(\mathbb{E}[X_H]\ge320/9-3(80/9)=80/9\). Dividing by \(p^4=(8/9)^4=4096/6561\) gives \[ \operatorname{cr}(K_{10})\ge \frac{80}{9}\cdot\frac{6561}{4096} =\frac{3{,}645}{256}, \] which agrees with the direct calculation.
Worked Example: A Graph on Twelve Vertices with 48 Edges
Take \(V(G)=\mathbb{Z}_{12}\), with arithmetic modulo \(12\), and define \[ E(G)=\bigl\{\{i,i+k\pmod {12}\}: i\in\mathbb{Z}_{12},\ k\in\{1,2,3,4\}\bigr\}. \] This is a simple graph: reversing an edge would require an offset in \(\{8,9,10,11\}\), not in \(\{1,2,3,4\}\), so the listed edges are not duplicated. Every vertex is adjacent to the four vertices at offsets \(1,2,3,4\) and the four at offsets \(-1,-2,-3,-4\). These eight neighbors are distinct, so every degree is \(8\). The degree sum is \(12\cdot8=96\), and each edge contributes two to that sum; therefore \(m=96/2=48\).
Here \(n=12\) and \(m=48=4n\), so the lemma applies at the threshold. It gives
Check: the edge count can also be read directly from the definition: there are \(12\cdot4=48\) listed pairs, with no duplicates as verified above. The degree-sum count independently gives \(48\) edges. The hypothesis is met with equality, \(48=4\cdot12\), and the computed lower bound is exactly \(12\).
Worked Example: The Complete Bipartite Graph \(K_{10,10}\)
Let \(A=\{a_1,\ldots,a_{10}\}\), \(B=\{b_1,\ldots,b_{10}\}\), \(V(G)=A\cup B\), and \(E(G)=\{a_i b_j:1\le i\le10,\ 1\le j\le10\}\). Each of the ten vertices in \(A\) is joined to all ten vertices in \(B\), and there are no other edges. Thus \(n=20\) and \(m=10\cdot10=100\). Since \(100\ge4\cdot20=80\), the Crossing Lemma applies.
Substitution gives
Because the crossing number is an integer and \(39\cdot16=624<625\), this proves \(\operatorname{cr}(K_{10,10})\ge40\). The edge count is independently confirmed by summing degrees: all 20 vertices have degree 10, so the degree sum is \(20\cdot10=200\), giving \(200/2=100\) edges.
Why the Bound Is Useful—and a Common Error
The planar edge bound only says that a graph drawn with few or no crossings cannot have too many edges. The Crossing Lemma makes the obstruction quantitative: once \(m\ge4n\), the number of crossings is at least a constant multiple of \(m^3/n^2\). Thus a dense graph cannot be made nearly planar merely by choosing a more careful drawing. The lemma is a lower bound, not generally an exact crossing-number formula.
Common mistake: counting a crossing with probability \(p^4\) without checking its endpoints. The probability \(p^4\) is correct only when the crossing edges have four distinct endpoints. If two adjacent edges cross, retaining their three distinct endpoints keeps that crossing with probability \(p^3\), not \(p^4\). For example, when \(p=1/2\), these probabilities are \(1/8\) and \(1/16\), respectively. Applying \(p^4\) to such a crossing would underestimate its survival probability and invalidate the expectation identity. The correction is to use a minimum drawing with no adjacent-edge crossings, as in the proof.
A second common error is to use \(p\) as the survival probability of an edge. In vertex sampling, an edge survives only if both endpoints survive, so its probability is \(p^2\). Keeping these probabilities distinct is essential: vertices contribute \(pn\), edges contribute \(p^2m\), and crossings with four distinct endpoints contribute \(p^4\operatorname{cr}(G)\).
Check Your Understanding
For each question, verify both the hypotheses and any numerical calculation.
- Why does the proof require \(n\ge1\), and what condition ensures that \(p=4n/m\) is at most one?
- In the sampling proof, what are the survival probabilities of a vertex, an edge, and a crossing with four distinct endpoints?
- A simple graph has \(n=15\) vertices and \(m=60\) edges. Does the Crossing Lemma apply, and what lower bound does it give?
- Explain why a crossing between adjacent edges would not survive vertex sampling with probability \(p^4\).
- In the planarization bound, why can deleting at most one edge per crossing produce a planar graph?