crossing number of complete graph

Question

For a complete graph $K_n$, Show that

$$\frac{n^4}{80} + O(n^3) \;\;\leq\;\; \nu (K_n) \;\;\leq\;\; \frac{n^4}{64} + O(n^3),$$ where the crossing number $\nu (G)$ of a graph $G$ is the minimum number of edge-crossings in a drawings of $G$ in the plane.

I have searched but did not find any proof of this result. I am studying the book "Introduction to Graph Theory" by Duglas B. West. The proof was given in the book, but I am not able to understand the first paragraph of the proof.

Answer 1

The part of the proof you say you were confused by is a recursive argument, using a lower bound on $\nu(K_{n-1})$ to get a lower bound on $\nu(K_n)$. I'll give the first few values of $n$ as examples before going on to the general case.

We start with $\nu(K_5) \ge 1$, because $K_5$ is not planar, and therefore in any planar drawing, at least one pair of edges must cross.

---

To analyze $\nu(K_6)$, we take its $6$ vertices $\{v_1, v_2, v_3, v_4, v_5, v_6\}$ five at a time.

• In any drawing of $K_6$, we may take the positions of $\{v_1, v_2, v_3,v_4, v_5\}$ and the edges between them, and get a drawing of $K_5$. This must have one pair of crossing edges.
• We can also take the positions of $\{v_1, v_2, v_3, v_4, v_6\}$ and the edges between them, and get a different drawing of $K_5$. This must also have one pair of crossing edges.
• Repeating this for $\{v_1, v_2, v_3, v_5, v_6\}$, $\{v_1, v_2, v_4, v_5, v_6\}$, $\{v_1, v_3, v_4, v_5, v_6\}$, and $\{v_2, v_3, v_4, v_5,v_6\}$, we get four more pairs of crossing edges.

So we've counted $6$ pairs of crossing edges total. However, we may have counted the same pair of crossing edges multiple times: for example, if the edges $v_1 v_2$ and $v_3 v_4$ cross, we could have counted that once for $\{v_1, v_2, v_3, v_4, v_5\}$, and again for $\{v_1, v_2, v_3, v_4, v_6\}$.

However, we could have counted the crossing pair $v_1 v_2$ and $v_3 v_4$ only twice: only two of our groups of $5$ vertices include $\{v_1, v_2, v_3, v_4\}$. Similarly, any other crossing pair was counted at most twice. So if we have counted $6$ crossing pairs, each one counted at most twice, then there must actually be at least $3$ distinct pairs: $\nu(K_6) \ge 3$.

---

To analyze $\nu(K_7)$, we take its $7$ vertices $\{v_1, v_2, v_3, v_4, v_5, v_6, v_7\}$ six at a time.

• As before, in any drawing of $K_7$, we may take the positions of $\{v_1, v_2, v_3, v_4, v_5, v_6\}$ and the edges between them, and get a drawing of $K_6$. Since $\nu(K_6) \ge 3$, there must be at least $3$ crossings here.
• There are $7$ ways to pick which vertex to exclude, so our drawing of $K_7$ contains $7$ subdrawings of $K_6$, each one containing at least $3$ crossings.

As before, if we wrote down all the crossings we saw at each step, we'd write down at least $21$ crossings, because we get $3$ crossings at each of the $7$ steps. However, as before, each crossing got counted multiple times.

Here, it's possible to triple-count each crossing (but no more). If a $K_6$ counted the crossing pair $(v_1 v_2, v_3 v_4)$, we know that the vertex left out of that $K_6$ could be any of $v_5$, $v_6$, or $v_7$: three options.

To fix the triple counting, we divide $21$ by $3$ and conclude that $\nu(K_7) \ge \frac{21}{3} = 7.$

---

To run this argument for general $n$, we need to answer two questions:

1. How many crossings do we get when we count the crossings in each copy of $K_{n-1}$?

   We have $n$ ways to choose which vertex to leave out to get a drawing of $K_{n-1}$ from our drawing of $K_n$. Each drawing of $K_{n-1}$ contains at least $\nu(K_{n-1})$ crossings, so we count a total of $n \cdot \nu(K_{n-1})$ crossings.

2. How many times could we have we counted the same crossing?

   If a crossing between edges $v_a v_b$ and $v_c v_d$ was counted by one of these $K_{n-1}$'s, then none of the vertices $\{v_a, v_b, v_c, v_d\}$ could have been left out. This means there were $n-4$ choices of which vertex to leave out, and this crossing got counted $n-4$ times.

So this argument tells us $\nu(K_{n}) \ge \frac{n}{n-4} \cdot \nu(K_{n-1})$.

Solving the recursion starting from $\nu(K_5) = 1$ gives us $$\nu(K_n) \ge \frac{n(n-1)(n-2)(n-3)}{120} = \frac{n^4}{120} + O(n^3).$$ (This is easy to prove by induction.) Improving the constant from $\frac{1}{120}$ to $\frac{1}{80}$ is left as an exercise somewhere at the end of that chapter.