Math Conjectures

Harary–Hill Conjecture for the Crossing Number of KnK_n

OPENMajorExact constant problemProposed 1960–1963 · Standard version

Canonical statement

Let cr⁡(G)\operatorname{cr}(G) be the minimum number of pairwise edge crossings over plane drawings of a graph GG in general position. For every integer n≥1n\geq1,
cr⁡(Kn)=14⌊n2⌋⌊n−12⌋⌊n−22⌋⌊n−32⌋. \operatorname{cr}(K_n)= \frac14 \left\lfloor\frac n2\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.
View source LaTeX
Let \(\operatorname{cr}(G)\) be the minimum number of
pairwise edge crossings over plane drawings of a graph \(G\) in general
position. For every integer \(n\geq1\),
\[
  \operatorname{cr}(K_n)=
  \frac14
    \left\lfloor\frac n2\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.
\]
GRAPH-013:[Guy1960Crossing][Guy1972Crossing][Radziszowski2024Crossing]
Graph theoryGeometry and topology

Notes

This problem asks for the exact crossing number of the complete graph. The Harary–Hill conjecture states that cr⁡(Kn)\operatorname{cr}(K_n) equals 14⌊n/2⌋⌊(n−1)/2⌋⌊(n−2)/2⌋⌊(n−3)/2⌋\tfrac14\lfloor n/2\rfloor\lfloor (n-1)/2\rfloor\lfloor (n-2)/2\rfloor\lfloor (n-3)/2\rfloor for every n≥1n\geq 1. The formula and the problem date to the early 1960s, appearing in Guy's work [Guy1960Crossing], with the now-standard formulation fixed shortly afterwards.

The conjectured value is achieved by explicit drawings, so it is an upper bound for all nn; the open direction is the matching lower bound. Equality has been verified for small values of nn [Guy1972Crossing], and it is also known to hold within certain restricted classes of drawings, where the conjectured count cannot be beaten. The state of the art for this and related crossing-number problems is collected in a recent survey [Radziszowski2024Crossing].

A resolution requires either a lower-bound argument matching the known drawings for all nn, or a drawing of some KnK_n with fewer crossings; neither is known, and the problem remains open.

References (3)

The boxed statement is the canonical open formulation — not a stronger variant or a related research program. The status reflects the catalog's last review; do your own literature search before investing serious effort.