The proof of the Harary--Hill conjecture: a detailed exposition and an extension to rotation systems
Abstract
The Harary--Hill conjecture states that the crossing number ucrKn of the complete graph Kn is Z(n):=1/4⌊n/2⌋⌊(n−1)/2⌋⌊(n−2)/2⌋⌊(n−3)/2⌋ for all n≥ 3. In October 2026 OpenAI uploaded to GitHub a proof of this conjecture. The proof is very short, but it relies on polynomial methods that are not part of the standard techniques used by many combinatorialists, and it is written with very little motivation or explanation. Since we found the proof very hard to follow, we decided to write this paper, which contains a complete proof of the conjecture written for mathematicians who are more familiar with combinatorics than with polynomial methods. In fact we prove a more general result on rotation systems of Kn, from which the Harary--Hill conjecture easily follows. Namely, we show that for every rotation system Π of Kn the number of $4$-vertex subsystems of Π realizable as drawings of K4 with one crossing, plus three times the number of non-realizable $4$-vertex subsystems of Π, is at least Z(n). The statement and proof of our result are purely combinatorial and do not involve drawings at all.
Related
- Some results on Archdeacon's conjecture for rotation systems
- Proof of the Harary--Hill conjecture: an exposition
- 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
- Global Convergence of Detailed Balanced Mass Action Systems
BibTeX
@misc{salazar2026proof,
title = {{The proof of the Harary--Hill conjecture: a detailed exposition and an extension to rotation systems}},
author = {Gelasio Salazar},
howpublished = {arXiv},
year = {2026},
month = nov,
doi = {10.48550/arxiv.2611.03515},
eprint = {2611.03515},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2611.03515},
}
RIS
TY - UNPB
TI - The proof of the Harary--Hill conjecture: a detailed exposition and an extension to rotation systems
AU - Gelasio Salazar
PY - 2026
DA - 2026/11/02
PB - arXiv
DO - 10.48550/arxiv.2611.03515
UR - https://arxiv.org/abs/2611.03515
AB - The Harary--Hill conjecture states that the crossing number ucrK_n of the complete graph K_n is Z(n):=1/4⌊n/2⌋⌊(n−1)/2⌋⌊(n−2)/2⌋⌊(n−3)/2⌋ for all n≥ 3. In October 2026 OpenAI uploaded to GitHub a proof of this conjecture. The proof is very short, but it relies on polynomial methods that are not part of the standard techniques used by many combinatorialists, and it is written with very little motivation or explanation. Since we found the proof very hard to follow, we decided to write this paper, which contains a complete proof of the conjecture written for mathematicians who are more familiar with combinatorics than with polynomial methods. In fact we prove a more general result on rotation systems of K_n, from which the Harary--Hill conjecture easily follows. Namely, we show that for every rotation system Π of K_n the number of $4$-vertex subsystems of Π realizable as drawings of K_4 with one crossing, plus three times the number of non-realizable $4$-vertex subsystems of Π, is at least Z(n). The statement and proof of our result are purely combinatorial and do not involve drawings at all.
ER -