PreprintCC BY 4.0arXiv
Proof of the Harary--Hill conjecture: an exposition
Abstract
The Harary--Hill conjecture states that the crossing number of the complete graph Kn is exactly 1/4⌊n/2⌋ ⌊(n−1)/2⌋ ⌊(n−2)/2⌋ ⌊(n−3)/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
- The proof of the Harary--Hill conjecture: a detailed exposition and an extension to rotation systems
- The Erdős--Sós Conjecture: A visual exposition of the proof discovered by GPT-6 Astra
- The geometric case of the Erdős Similarity Conjecture. A human exposition of the OpenAI proof
- Bourgain's proof of the circular maximal theorem: an exposition
- A short proof of a quadratic lower bound on the border determinantal complexity of x1n+⋯+xnn over ℂ: A simple human exposition
BibTeX
@misc{balko2026proof,
title = {{Proof of the Harary--Hill conjecture: an exposition}},
author = {Martin Balko},
howpublished = {arXiv},
year = {2026},
month = oct,
doi = {10.48550/arxiv.2610.34444},
eprint = {2610.34444},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2610.34444},
note = {CC BY 4.0},
}
RIS
TY - UNPB
TI - Proof of the Harary--Hill conjecture: an exposition
AU - Martin Balko
PY - 2026
DA - 2026/10/25
PB - arXiv
DO - 10.48550/arxiv.2610.34444
UR - https://arxiv.org/abs/2610.34444
AB - The Harary--Hill conjecture states that the crossing number of the complete graph K_n is exactly 1/4⌊n/2⌋ ⌊(n−1)/2⌋ ⌊(n−2)/2⌋ ⌊(n−3)/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.
ER -