Proof of the Harary--Hill conjecture: an exposition
math.CO
Submitted: 2026-10-25
Updated: 2026-11-05
Comments: 16 pages, updated reference and minor improvements
License: http://creativecommons.org/licenses/by/4.0/
The gist: The Harary--Hill conjecture states that the crossing number of the complete graph K n is exactly 1 over 4 n over 2 n-1 over 2 n-2 over 2 n-3 over 2.
Abstract
The Harary--Hill conjecture states that the crossing number of the complete graph K n is exactly 1 over 4 n over 2 n-1 over 2 n-2 over 2 n-3 over 2. We present a streamlined variant of the proof of this conjecture recently announced by OpenAI (2026). Although the original proof is relatively short, it is quite difficult to follow. We simplify several steps and provide a concise and accessible exposition of the proof. We also combine this new result with known reductions to determine the crossing numbers of several other graph families.
Related papers
- Three-ends Furstenberg estimates and approximate rectangles
- Multicolor Ramsey numbers of ordered matchings
- Exponential random graph models with soft clique constraints
- A Full-Sequence Quantitative Gap Between the Chromatic and Cochromatic Numbers of a Random Graph
- Ehrhart positivity for paving positroids
- Nonlinear lower-tail large deviations at criticality