The crossing number of the complete graph minus an edge
Abstract
We prove that for every integer n >= 2 and every edge e of the complete graph K_n, the ordinary crossing number is cr(K_n-e) = (1/4) floor((n+2)/2) floor((n-1)/2) floor((n-3)/2) floor((n-4)/2), which was conjectured by Zheng, Lin, Yang and Cui in 2007. The proof relies on the September 2026 OpenAI preprint proving the Harary–Hill formula for cr(K_n), whose stated results we use without re-proving them. Given that formula, the even orders follow from a theorem of Ouyang, Wang and Huang (2014), equivalently of Chia and Lee (2015), and the odd orders n <= 13 follow from their counting bound and integrality. The new content is the lower bound for odd n >= 15. We adapt the polynomial rank method of the OpenAI preprint to the missing edge. The adaptation restricts the test polynomials so that they put no weight on the missing pair. It pairs two different vanishing subspaces by mixed orthogonality. It also localizes, with a twisted detector that needs the full rectangular nonsingularity statement of the preprint, only at the vertices whose stars are complete. Via the product identity of Ouyang, Wang and Huang, the formula gives the crossing number of K_m square P_n conjectured by Zheng et al. for all m >= 4 and n >= 1, where P_n is the path with n edges. The new lower-bound input enters this consequence for odd m >= 13 and n >= 2; the literature comparison is bounded as stated in the novelty section of the paper.
Comments
This is an AI-assisted preprint with internal independent agent proof, contribution and manuscript reviews, not external peer review. Supporting Lean material is partial and does not formalize the complete theorem. Mathematical results from OpenAI/math at revision fd4aeeb2ee4fc729c18d98444fed42fd0529eeeb are stipulated premises, with exact source interfaces and other credited inputs disclosed in the paper. The literature comparison is bounded and does not certify worldwide priority. 47 supporting Lean theorems and 17 definitions cover finite tensor kernels, dimensions, diagonal nondegeneracy, mixed tests, twisted detection, localization budgets and conditional descent. Drawing topology, concrete substitutions, divisibility, instantiated descent/injections, orientation/count comparison, even/upper assembly and product theorem remain prose. U4 is an explicit premise, not a proved upstream theorem or new axiom. Supporting package will be linked after Zenodo publication. Paper/prose CC BY 4.0; original code/Lean MIT.