Diameter graphs of polygons and the proof of a conjecture of Graham (Q2459503): Difference between revisions

In 1922, \textit{K. Reinhardt} [Jahresber. Deutsch. Math.-Verein. 31, 251--270 (1922)] proved that for \(n\) odd the regular \(n\)-gon has the maximum area among all \(n\)-gons with unit diameter, while there are infinitely many quadrilaterals with unit diameter and the same area as the square of side \(1/\sqrt{2}\). In 1975, \textit{R. L. Graham} [J. Combin. Theory, Ser. A 18, 165--170 (1975; Zbl 0299.52006)] conjectured that the diameter graph of a unit diameter \(2n\)-gon with maximal area has a cycle of length \(2n-1\) and one additional edge from the remaining vertex. In this interesting paper one may find a proof of this conjecture. First it is shown that the diameter graph of an extremal \(2n\)-gon cannot be a path or a tree. Then the authors derive an isodiametric theorem for fixed-diameter polygons whose diameter graphs contain a cycle of given length. The final step of the proof consists in constructing a \(2n\)-gon whose area is larger than that of any \(2n\)-gon whose diameter graph contains a cycle of length less than \(2n-1\). Most of the results used in proof were already available in the first half of the 20th century, the only newer tool being a computer algebra system needed to check that a certain combination of trigonometric functions is positive on a specific domain. The paper ends with two open questions, namely, whether the \(2n\)-gon of unit diameter and maximal area is unique or symmetric about the diameter that is not in the cycle of the diameter graph.