The Harary-Hill conjecture, also called Guy's conjecture (Schaefer 2021, p. 42), states that the graph crossing number complete
graph positive integer
(1)
where floor function (Harary and Hill 1963). The
conjectured value
(2)
The values for A028723 ), while the verified
crossing numbers A000241 .
Guy (1972) proved the conjecture for
For odd good drawing
(3)
This parity result is due to Kleitman (1976). Counting each graph crossing in the vertices
gives
(4)
for ceiling function (Pan and Richter 2007).
Consequently, if the conjecture holds for odd
Some optimal good drawings of good
drawings of
OpenAI (2026) announced a proof that formula .
Balko (2026) subsequently presented a specialist exposition of the announced proof ,
simplifying parts of the original argument. This extends the earlier inspection of
the formal statement reported by VibeMathed (2026), but an independent audit of the
complete formalization has not been established.
Balogh et al. (2026) improved the asymptotic lower
bound to
(5)
as et al. (2026) report ChatGPT assistance with correctness checks in
part of the proof .
See also Complete Bipartite Graph ,
Complete Graph ,
Graph
Crossing Number ,
Zarankiewicz's Conjecture
Explore with Wolfram|Alpha
References Aichholzer, O. "Another Small but Long Step for Crossing Numbers: Proc. 33rd Canadian Conference on Computational Geometry (CCCG 2021) (Ed.
M. He and D. Sheehy). Halifax, Nova Scotia, Canada, pp. 72-77, 2021.
https://publications.ist.tugraz.at/abstracts/a-aslscn-21/index.html . Balko,
M. "Proof of the Harary-Hill Conjecture: An Exposition." 25 Oct 2026. https://arxiv.org/abs/2610.34444 . Balogh,
J.; Layman, N.; Lidický, B.; Pfender, F.; Salazar, G.; Spiro, S.; and Volec,
J. "Crossing Numbers of Complete Bipartite Graphs." 18 Oct 2026. https://arxiv.org/abs/2610.25204 . Brodsky,
A.; Durocher, S.; and Gethner, E. "The Rectilinear Crossing Number of Elec. J. Combin. 8 , R23, 2001.
https://doi.org/10.37236/1567 . de
Klerk, E.; Maharry, J.; Pasechnik, D. V.; Richter, R. B.; and Salazar,
G. "Improved Bounds for the Crossing Numbers of SIAM J. Discr. Math. 20 , 189-202, 2006.
https://doi.org/10.1137/S0895480104442741 . de
Klerk, E.; Pasechnik, D. V.; and Schrijver, A. "Reduction of Symmetric
Semidefinite Programs Using the Regular Math. Program. 109 , 613-624,
2007. Guy, R. K. "The Crossing Number of the Complete Graph."
Bull. Malayan Math. Soc. 7 , 68-72, 1960. Guy, R. K.
"Crossing Numbers of Graphs." In Graph
Theory and Applications: Proceedings of the Conference at Western Michigan University,
Kalamazoo, Mich., May 10-13, 1972 Harary,
F. and Hill, A. "On the Number of Crossings in a Complete Graph." Proc.
Edinburgh Math. Soc. 13 , 333-338, 1963. https://doi.org/10.1017/S0013091500025645 . Kleitman,
D. J. "A Note on the Parity of the Number of Crossings of a Graph."
J. Combin. Th., Ser. B 21 , 88-89, 1976. https://doi.org/10.1016/0095-8956(76)90032-0 . OpenAI.
"The Crossing Number of Complete Graphs." Sep. 23, 2026. https://github.com/openai/math/blob/adc7f1241b42e322a6451854ab7e4b4c146bf78a/preprints/The-crossing-number-of-complete-graphs-September-23-2026/paper.pdf . Pan,
S. and Richter, R. B. "The Crossing Number of J. Graph Th. 56 , 128-134,
2007. https://doi.org/10.1002/jgt.20249 . Schaefer,
M. "The Graph Crossing Number and Its Variants: A Survey." Elec. J.
Combin. , Dynamic Survey DS21, 6th ed., May 21, 2021. https://doi.org/10.37236/2713 .
https://www.combinatorics.org/files/Surveys/ds21/ds21v6-2021.pdf . Sloane,
N. J. A. Sequences A000241 /M2772
and A028723 in "The On-Line Encyclopedia
of Integer Sequences." VibeMathed. "The Harary-Hill Conjecture
on the Crossing Number of Complete Graphs." Oct. 7, 2026. https://vibemathed.com/problem/harary-hill-conjecture .
Cite this as:
Weisstein, Eric W. "Harary-Hill Conjecture."
From MathWorld https://mathworld.wolfram.com/Harary-HillConjecture.html
Subject classifications More... Less...
of the complete
graph 
,
for a positive integer 
, satisfies
is the floor function (Harary and Hill 1963). The
conjectured value 
can also be written as
,
2, ... are then given by 0, 0, 0, 0, 1, 3, 9, 18, 36, 60, 100, 150, 225, 315, 441,
588, ... (OEIS A028723), while the verified
crossing numbers 
are tabulated in OEIS A000241.
, a result extended to 
by Pan and Richter (2007) and to 
by Aichholzer (2021).
,
any good drawing 
of 
satisfies
subdrawings that retain its four vertices
gives
![cr(K_n)>=[(ncr(K_(n-1)))/(n-4)]](/images/equations/Harary-HillConjecture/NumberedEquation4.svg)
,
where ![[x]](/images/equations/Harary-HillConjecture/Inline16.svg)
is the ceiling function (Pan and Richter 2007).
Consequently, if the conjecture holds for odd 
, it also holds for 
.
cannot be extended to optimal good
drawings of 
(Pan and Richter 2007).
for every 
, attributed to an unreleased internal OpenAI model. The release
supplies a Lean formalization of the complete formula.
Balko (2026) subsequently presented a specialist exposition of the announced proof,
simplifying parts of the original argument. This extends the earlier inspection of
the formal statement reported by VibeMathed (2026), but an independent audit of the
complete formalization has not been established.
.
Balogh et al. (2026) report ChatGPT assistance with correctness checks in
part of the proof.
and 
."
In Proc. 33rd Canadian Conference on Computational Geometry (CCCG 2021) (Ed.
M. He and D. Sheehy). Halifax, Nova Scotia, Canada, pp. 72-77, 2021.
Is 62." Elec. J. Combin. 8, R23, 2001.
and 
." SIAM J. Discr. Math. 20, 189-202, 2006.
-Representation." Math. Program. 109, 613-624,
2007.Guy, R. K. "The Crossing Number of the Complete Graph."
Bull. Malayan Math. Soc. 7, 68-72, 1960.Guy, R. K.
"Crossing Numbers of Graphs." In 
Is 100." J. Graph Th. 56, 128-134,
2007.