Harary-Hill Conjecture

The Harary-Hill conjecture, also called Guy's conjecture (Schaefer 2021, p. 42), states that the graph crossing number of the complete graph , for a positive integer , satisfies

(1)

where is the floor function (Harary and Hill 1963). The conjectured value can also be written as

$Z(n)={1/(64)n(n-2)^2(n-4) for n even; 1/(64)(n-1)^2(n-3)^2 for n odd.$

(2)

The values for , 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.

Guy (1972) proved the conjecture for , a result extended to by Pan and Richter (2007) and to by Aichholzer (2021).

For odd , any good drawing of satisfies

(3)

This parity result is due to Kleitman (1976). Counting each graph crossing in the subdrawings that retain its four vertices gives

(4)

for , where is the ceiling function (Pan and Richter 2007). Consequently, if the conjecture holds for odd , it also holds for .

Some optimal good drawings of cannot be extended to optimal good drawings of (Pan and Richter 2007).

OpenAI (2026) announced a proof that 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) improved the asymptotic lower bound to

(5)

as .

Salazar (2026) gives a detailed exposition and extends the bound to abstract rotation systems of , for . Let count four-vertex subsystems realizable by a good drawing of with one crossing, and let count those not realizable by any good drawing of . Then

(6)

For the rotation system induced by a good drawing , and , recovering the crossing bound. The stronger inequality with coefficient 1 in place of 3 remains conjectural.

Explore with Wolfram|Alpha

More things to try:

References

Aichholzer, O. "Another Small but Long Step for Crossing Numbers:

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. 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

Is 62." 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

and

." 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

-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 Graph Theory and Applications: Proceedings of the Conference at Western Michigan University, Kalamazoo, Mich., May 10-13, 1972 (Ed. Y. Alavi, D. R. Lick, and A. T. White). New York: Springer-Verlag, pp. 111-124, 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

Is 100." J. Graph Th. 56, 128-134, 2007. https://doi.org/10.1002/jgt.20249.Salazar, G. "The Proof of the Harary-Hill Conjecture: A Detailed Exposition and an Extension to Rotation Systems." 2 Nov 2026. https://arxiv.org/abs/2611.03515v1.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--A Wolfram Resource. https://mathworld.wolfram.com/Harary-HillConjecture.html

Harary-Hill Conjecture

See also

Explore with Wolfram|Alpha

References

Cite this as:

Subject classifications