Harary–Hill conjecture for the crossing number of complete graphs

At least 12 years old · documented by

Let KnK_n be the complete graph on nn vertices, and define

H(n):=14⌊n2⌋⌊n−12⌋⌊n−22⌋⌊n−32⌋.H(n):=\frac{1}{4}\left\lfloor\frac{n}{2}\right\rfloor\left\lfloor\frac{n-1}{2}\right\rfloor\left\lfloor\frac{n-2}{2}\right\rfloor\left\lfloor\frac{n-3}{2}\right\rfloor.

Here cr⁡(G)\operatorname{cr}(G) denotes the minimum number of crossings in a plane drawing of a graph GG. Harary–Hill conjecture.

cr⁡(Kn)=H(n).\operatorname{cr}(K_n)=H(n).

The formula is achieved by Hill's drawing of KnK_n and is conjectured to be optimal; determining the crossing number of complete graphs remains a central open problem in topological graph theory.

References

Primary source

Ruy Fabila-Monroy, Rosna Paul, Jenifer Viafara-Chanchi and Alexandra Weinberger, “On the rectilinear crossing number of complete balanced multipartite graphs and layered graphs”, arXiv:2404.13155 (2025).

Additional references

5 papers in this index state this conjecture (2013–2024). The statement above is taken from the most recent of them; the others are arXiv:1907.07796, arXiv:1805.06780, arXiv:1803.07515, arXiv:1307.3297.

Progress summary

Never refreshed

Nothing recorded yet. Refresh searches the literature and the public web for attempts on this problem, and writes the first summary here.

Solutions 1

RemarkAI-assistedClaimed by OpenAI.See full solutionHide full solution

Claimed by OpenAI.

Claims the ordinary crossing number of K_n equals one quarter of floor(n/2) floor((n-1)/2) floor((n-2)/2) floor((n-3)/2) for every positive integer n, with unrestricted vertex positions and edge routes.

Repository: https://github.com/openai/math

Manuscript: https://github.com/openai/math/blob/adc7f1241b42e322a6451854ab7e4b4c146bf78a/preprints/The-crossing-number-of-complete-graphs-September-23-2026/paper.pdf

  • OpenAI-165-01-The-crossing-number-of-complete-graphs.pdf361,680 bytesOpen