**The Crossing Number of
the Complete Graph **

A *drawing* of a graph in the plane has the vertices placed at distinct
points and the edges represented by homeomorphs of [0,1] joining their endpoints such that:

- no edge contains a vertex other than its endpoints,
- no two adjacent edges share a point other than their common endpoint, and
- two nonadjacent edges share at most one point at which they cross transversally.

The *crossing number* of *G*, *cr**(**G)*,
is the minimum number of pairwise crossings over all
planar drawings.

**Conjecture**: Cr(K_n
) = (1/4) [n/2] [(n-1)/2] [(n-2)/2] [(n-3)/2]* where *[m]* is the
integer part of m.*

This conjectured crossing number is known to be an upper bound. This is
shown by exhibiting a drawing with the desired number of crossings. To wit,
when *n = 2m*, place *m* vertices regularly spaced along both the top
and bottom of a tin can (a cylinder homeomorphic to a
sphere). Two vertices along the top are connected along the lid with a straight
line segment. Likewise for two vertices along the bottom rim.
A vertex on the top is connected to one on the bottom with a lateral line
segment of minimum possible positive winding number around the cylinder. A
count reveals that the number of crossings in this drawings
achieves the conjectured minimum. For *n = 2m-1* we delete one vertex from
the drawing described and achieve the conjectured minimum.

The conjecture is known to be true for *n* at most 10 (see [G]). I
believe it is also known to hold for *n* at most 12, but I am unsure of
the reference. If the conjecture is true for *n = 2m*, then it is also
true for *n-1*. This follows from an argument counting (with
multiplicities) the number of crossings in a drawing of all *K_{n-1}*'s contained in an optimal drawing of *K_n*.

Some partial progress is possible by showing that the conjectured upper
bound is asymptotically correct, that is, that *lim**
cr(K_n)/n^4 = 1/64*. The
best known upper bound is due to Kleitman [K], who
shows that this limit is at least 3/240. His result is based on a counting
argument similar to that described above. This was recently improved, when
[KPRS] showed that the crossing number of K_n is at
least .83 of its conjectured value.

**References**

[G] R. Guy, The decline and fall of Zarankiewicz's
theorem, in *Proof Techniques in Graph Theory* (F. Harary
Ed.), Academic Press, New York (1969) 63-69.

[K] D. Kleitman, The crossing number of *K_{5,n}*, *J. Combin. Theory*
**9** (1970) 315-323.

[KPRS] E. de Klerk, D. Pasechnik, R.B. Richter, and G. Salazar, personal communication.

Submitted by : Dan Archdeacon, Department of Mathematics and Statistics, University of Vermont, Burlington VT 05405 USA

Send comments to *dan.archdeacon@uvm.edu
*

August, 1995, modified December 2003