← All problems

The crossing-number formula for a complete graph with one edge removed

Let KnK_n be the complete graph on n≥2n\ge2 vertices, and let ee be any edge. Write cr⁡(G)\operatorname{cr}(G) for the ordinary planar crossing number: the minimum number of crossing points over drawings of GG by simple arcs, with no restriction that edges be straight or lie in prescribed pages. Zheng–Lin–Yang–Cui conjecture. Is

cr⁡(Kn−e)=14⌊n+22⌋⌊n−12⌋⌊n−32⌋⌊n−42⌋\operatorname{cr}(K_n-e)=\frac14\left\lfloor\frac{n+2}{2}\right\rfloor\left\lfloor\frac{n-1}{2}\right\rfloor\left\lfloor\frac{n-3}{2}\right\rfloor\left\lfloor\frac{n-4}{2}\right\rfloor

for every n≥2n\ge2? The displayed quantity is zero for 2≤n≤52\le n\le5. This is the missing-edge conjecture recorded by Ouyang–Wang–Huang and by the Clancy–Haythorpe–Newcombe survey, Conjecture 2.20. It is distinct from the Harary–Hill formula for KnK_n and from the bipartite missing-edge problem.

References

W. Zheng, X. Lin, Y. Yang and C. Cui, On the crossing number of K_m □ P_n, Graphs Combin. 23 (2007), 327–336. https://doi.org/10.1007/s00373-007-0726-z Z. Ouyang, J. Wang and Y. Huang, The crossing number of the Cartesian product of paths with complete graphs, Discrete Math. 328 (2014), 71–78, Section 1, displays (1.1)–(1.2). https://doi.org/10.1016/j.disc.2014.03.011 K. Clancy, M. Haythorpe and A. Newcombe, A survey of graphs with known or bounded crossing numbers, arXiv:1901.05155v5, Conjecture 2.20. https://arxiv.org/abs/1901.05155v5 Attribution to the 2007 paper follows the latter two sources; the original 2007 text was not directly consulted in preparing this record.

Progress summary

Refreshed
Open · progress reported

The formula is proved through eight vertices, while later extensions remain conditional and unverified.

The Zheng–Lin–Yang–Cui conjecture asks whether the stated formula gives the ordinary crossing number of a complete graph after deleting one edge for every n≥2n\ge2. It was proposed in 2007 and later recorded as Conjecture 2.20 in the Clancy–Haythorpe–Newcombe survey.

Known results

  • Zheng, Lin, Yang and Cui proved the formula for n≤8n\le8 (2007).
  • Ouyang, Wang and Huang extended the range through n≤12n\le12, conditional on the Harary–Hill formula (2014).
  • The 2020 survey records the general conjecture as open.

October–November 2026 conditional developments

An October 2026 exposition reports a claimed proof of the Harary–Hill formula, which would imply the missing-edge formula in the even-order cases, but the claim is unverified. A submission dated November 7, 2026 argues conditionally for the full formula, claiming a new lower-bound range for odd n≥15n\ge15 and deriving the remaining cited cases from six stipulated inputs; it explicitly does not provide independent validation.

Current status (as of November 2026): The formula is proved for n≤8n\le8; extensions through n≤12n\le12, all even orders, and odd n≥15n\ge15 are conditional and unverified, so the full conjecture remains open.

Sources

Solutions 1

Conditional all-order formula for cr(K_n−e), assuming the pinned Harary–Hill theorem and five additional source interfaces. The new lower-bound range is odd n≥15; the full crossing theorem is not Lean-formalized.See full solutionHide full solution

Conditional result. The paper derives the displayed ordinary crossing-number formula for every n≥2, under six explicitly stated inputs from the pinned OpenAI complete-graph preprint: drawing normalization, cycle pairing, interpolation weights, rectangular detector nonsingularity, Harary–Hill, and the explicit upper drawing. The new lower-bound range is odd n≥15. Even orders and odd n≤13 are credited consequences of prior results once Harary–Hill is assumed. The proof modifies the missing-pair tests, mixed orthogonality and detector/localization argument; Harary–Hill alone is not its only premise.

Paper and package. The crossing number of the complete graph minus an edge; full supporting archive. The Cartesian-product corollary and its exact new range are stated in the manuscript.

Verification and source limits. The OpenAI inputs at revision fd4aeeb2ee4fc729c18d98444fed42fd0529eeeb are stipulated true. This is conditional progress, not an independent validation of those inputs. The 47 supporting Lean theorems certify scoped algebra only; drawing topology, concrete evaluation/descent bridges and all-order assembly remain in prose. The paper credits the 2007 conjecture through sources whose full statements were available, and discloses its bounded literature comparison. AI-assisted internal review is not external peer review or MathDB endorsement.