# Lower bound of crossing number (minimum) of K7

I am able to construct K7 with crossing number 9 from K6 with crossing number 3. Hence, I know the crossing number for K7 is at most 9; though, the number may not be sharp.

Now, I heard it is possible to prove the crossing number of K7 is at least 7 (also, may not be sharp). Anyone have any idea?

• The crossing numer of $K_7$ is exactly $9$, and it is known for $n \le 10$ that the crossing number of $K_n$ is $(1/4)[n/2][(n-1)/2][(n-2)/2][(n-3)/2]$ where each square bracket means the floor function. This formula is also known to be a general upper bound, and its being exact for $n \le 10$ was shown by R. Guy. See openproblemgarden.org/op/… Apr 22 '13 at 2:28
• I thought R. Guy (1972) proved (n^4)/80+O(n^3) <= nu(Kn) <= (n^4)/64+O(n^3), but the big-O notation doesn't help me here. I'll read your link carefully. Thanks.
– Sean
Apr 22 '13 at 4:13
• Actually I only scanned that the website referred to R. Guy as its backup for the conjectured formula being correct up to $n=10$, and another look shows that's been extended to $n=12$. However I got the impression that someone had shown these up to that point, since the article on the site made a careful distinction between upper/lower bounds and actual values. Apr 22 '13 at 4:37

Take a look at the Rectilinear Crossing Project for the current state of the art. Tight bounds and solutions are known up to $K_{27}$.
There are 3 essentially different ways to embed $K_7$ with 9 crossings, and these solutions are available at that site.