Four Questions about Drawing the Complete Graph

We ask four questions about drawings of the complete graph *K_n* in the plane. In a drawing non-adjacent edges are allowed to cross transversally at most once. An *empty triangle* in a drawing is a *K_3* such that all the remaining vertices lie on one side of the triangle.

**Question 1**: *What is the smallest number* t(n) *of empty triangles in a drawing of* K_n?

An upper bound of *t(n)* at most *2n-4* is known.

The next problem is in the spirit of Ester Klein or of Ramsey. There exists smallest numbers *m = Dr(K_n)* such that every drawing of *K_m* contains at least one subdrawing of *K_n* with the maximum number *n(n-1)(n-2)(n-3)/24* of crossings. It is known that *Dr(K_5)* is at least 11 and at most 113. See [HMS].

**Question 2**: *Does there exist a drawing of* K_11 *such that every subdrawing of* K_5 *has only one or three crossings?*

Let *h(s,n)* denote the minimum number of edges with at most *s* crossings in drawings of K_n. The following question is related to [HT].

**Question 3:** *For which values of* n *is* h(s,n) > 0? *Is* h(s,n) > 0 *for* n *at most* s*?*

The fourth question arises from [HM].

**Question 4:** *Does there exist a drawing of* K_n *with the maximum number of crossings such that a) at most one edge is without a crossing, or b) no edge is without a crossing*?

Harborth has a drawing of *K_n* (for each *n*) with two edges lacking crossings.

References

[HMS] H. Harborth, I. Mengersen, and R.H. Schelp, The drawing Ramsey number *Dr(K_n)*, *Australas. J. Combin. ***11** (1995) 151-156.

[HT] H. Harborth and C. Thurmann, Minimum number of edges with at most *s* crossings in drawings of the complete graph, *Congressus Numerantium* **102** (1994) 83-90.

[HM] H. Harborth and I. Mengersen, Drawings of the complete graph with maximum number of crossings, *Congressus Numerantium* **88** (1992) 225-228.

Submitted by : Heiko Harborth, Diskrete Mathematik, Technische Universitat Braunschweig, Pockelsstrasse 14, D-38106 Braunschweig, Germany

Send comments to *dan.archdeacon@uvm.edu *and to *h.harborth@tu-bs.de *

August, 1995