One of my favourite little theorems in combinatorial geometry is the following:
Theorem 1. Let be a set of points of diameter in the plane. Then the number of pairs in at distance is at most .
The following two figures show how diameter pairs can be attained:
The first one is based on an equilateral triangle, with some dangling edges added, and the second is based on a regular star heptagon, also with dangling edges.
Let’s translate Theorem 1 into graph-theoretical terms. Define a graph by letting the vertices be the points, and the edges the diameter pairs. Call this graph the diameter graph of the points. Theorem 1 states that a diameter graph on points has at most edges. Its proof is not difficult; try it! [Hint: All standard proofs are based on the fact that any two diameters necessarily intersect.] I would now like to explore the history of this theorem. In particular, who proved it first?
Many papers and books, starting with a 1946 paper of Paul Erdős, credit Heinz Hopf from Zürich and E. Pannwitz from Berlin (1934) with this theorem, sometimes in combination with J. W. Sutherland from Cambridge (1935). However, when these old references are examined, no such theorem occurs. In fact, Hopf and Pannwitz posed the following problem in 1934:
Let be distinct points in the plane such that the distance conditions
hold. Show that this is possible if is odd and impossible if is even and at least .
Two solutions were subsequently published in 1935: one by Sutherland and another by W. Fenchel (a well-known name in convexity). A list of other solvers appeared as well in the 1935 reference: A. E. Mayer (Vienna), H. Baer (Frankfurt), L. Ehrlich (Berlin), J. Fox (Brooklyn), R. Frucht (Triest), L. Goeritz (Rostock), F. Gruber (Vienna), J. Juilfs (Berlin), R. Lauffer (Graz), E. Linés Escardó (Madrid), P. Scherk (Göttingen), and W. Schulz (Berlin).
In graph-theoretical terms the problem asserts that:
Theorem 2. All cycles in a diameter graph in the plane are odd.
Does this imply Theorem 1? No. A graph without even cycles can have more edges than vertices (try to find some examples). However, it is well known that the upper bound for the number of edges is still linear: . [Hint: show that each block of at least three vertices in a graph with no even cycles consists of a single odd cycle.]
Thus Theorem 2 is unrelated to Theorem 1. However, both are easily deducible from the following statement, which is a characterisation of diameter graphs in the plane.
Theorem 3. Each connected component of a diameter graph in the plane is a path or a cycle that contains or is incident to every edge (i.e. a caterpillar with the head and tail possibly joined).
This can also be proved using the fact that any two edges intersect.
Back to Theorem 1. Who was the first to prove it? The oldest reference I can find is the 1946 paper of Erdős. So I would guess that he was the first to notice it, perhaps when he saw the problem of Hopf and Pannwitz and later recalled their problem incorrectly, thus giving them the credit. Who knows? The fact remains that the problem posed by Hopf and Pannwitz is about the nonexistence of even cycles, not about the maximum number of diameters.
- P. Erdős, On sets of distances of points, Amer. Math. Monthly 53 (1946), 248-250.
- H. Hopf and E. Pannwitz, Aufgabe Nr. 167, Jahresbericht Deutsch. Math.-Verein. 43 (1934), p. 114.
- J. W. Sutherland, Lösung der Aufgabe 167, Jahresbericht Deutsch. Math.-Verein. 45 (1935), 33- 35.
Thanks to Frank Bullock who helped me find the upper bound on the number of edges of a graph with no even cycles.