把每个点与其他所有点相连：最少交叉数终获证明

在一张纸上放五个点，用曲线把每一对点连起来：一共十条曲线。曲线可以随意弯曲，但不能穿过第三个点。试图避免一切交叉，你会失败。五个点时，至少有1个交叉无法避免；六个点时至少3个；十个点时至少60个。

数学家把这样的图称为完全图Kₙ的一个画法——n个点，每一对都相连——而任何画法所能达到的最少交叉数，称为它的交叉数。捷克查理大学的马丁·巴尔科（Martin Balko）称这个问题是“拓扑图论中最著名的问题之一”。

一位艺术家的计数

20世纪50年代末，英国艺术家安东尼·希尔（Anthony Hill）构造出了Kₙ的画法，其交叉数恰好为

Z(n) = ¼ ⌊n/2⌋ ⌊(n − 1)/2⌋ ⌊(n − 2)/2⌋ ⌊(n − 3)/2⌋

其中⌊ ⌋表示向下取整。认为没有任何画法能做得更好的猜测，最早由盖伊（Guy）发表，后来由哈拉里（Harary）和希尔讨论，并经埃尔德什（Erdős）和盖伊推广而广为人知。它被称为哈拉里–希尔猜想（Harary–Hill conjecture），或盖伊猜想。

这个公式增长得很快：

4个点或更少：0个交叉
5个点：1
7个点：9
10个点：60
14个点：315

六十年的部分答案

对每一个点数，都存在交叉数恰好为Z(n)的画法；难点在于证明没有任何画法能做得更好。

六十多年来，这一点只在特殊类型的画法中得到了证明——例如所有点都在一条直线上、每条曲线都保持在直线的同一侧；或者点都在球面上、每条曲线都走最短路径。巴尔科本人曾与Fulek和Kynčl一起解决过其中一类。到2021年，计算机已经验证该公式在14个点以内成立。对于数目非常大的点，最好的一般性结果先后保证了交叉数至少为Z(n)的98.5%，然后是98.99%。

一个证明，然后是一个更清晰的证明

2026年，OpenAI宣布给出了对任意点数都成立的证明；巴尔科的论文将其列为一篇“OpenAI Math Release preprint”，并把这个定理归功于它。论文没有说明那个证明是如何找到的。用巴尔科的话说，原证明“相对较短”，但“相当难以理解”。他的预印本给出了一个精简的变体，他写道，这个变体“只需要线性代数和图论的初等知识”。另一位数学家赫拉西奥·萨拉萨尔（Gelasio Salazar）正在准备另一份独立的详细阐述。

数系数，而不是数交叉

由于已知的画法已经达到Z(n)，只需要证明下界。证明分为四步。

只需考虑奇数。 一个最优画法可以重画，使共享一个点的曲线从不交叉；这样每个交叉都涉及4个不同的点。依次删去6个点中的每一个：剩下的每个5点图都至少有1个交叉，而每个交叉恰好在6次删除中的2次里保留下来（只要删去它自身4个点中的任意一个，它就消失；在另外2次删除中则保留下来）。因此交叉数的两倍至少为6：交叉数至少为3，这正是Z(6)。同样的计数对每个偶数都成立。
一族多项式。 给每个点一个各自的数。一个交叉涉及两条曲线，因此涉及四个点，也就是四个数。巴尔科使用四元多项式，并精心选取，使得当n为奇数时，这一族恰好有**Z(n)**个独立系数——7个点时为3 × 3 = 9。
交叉太少就留下了余地。 要求一个多项式在某个交叉处为零，就是一个方程。方程个数少于自由系数个数时，线性代数总能给出一个非零解。因此，一个交叉数少于Z(n)的画法，必然伴随着一个在其所有交叉处都为零的非零多项式；取其中次数最低的一个。
平面予以反击。 几何通过一个经典事实进入证明：平面上的一条闭合回路从右向左穿过另一条回路的次数，与从左向右穿过的次数恰好相等。选取合适的权重，由此得到一个由多项式取值构成、总和为零的平方和，其中一些项按正计，一些按负计。正项全都位于交叉处，而多项式在那里为零，所以负项也必须为零。再次运用这一回路事实，可以使它被一个固定因子整除；相除后得到一个次数更低、具有同样性质的非零多项式，而这是不可能的，因为我们取的已经是次数最低的那个。

那个符号论证是巴尔科最主要的改动：它取代了原证明中“涉及一个非退化双线性形式和正交补”的论证。他还用不同的方法证明了回路事实，并更直接地把每个点单独分离出来。

其他网络也随之解决

如果计数的不是交叉，而是至少相交一次的曲线对，或者相交奇数次的曲线对，答案仍然是Z(n)——只要共享一个点的曲线在别处从不相遇。结合早先的归约结果，这一定理还给出了以下几类图的精确交叉数：去掉若干条连线的完全图、沿一条路径或围绕一个偶圈串接起来的若干个完全图副本，以及一类称为扩展谢尔宾斯基图的类分形网络。

从6个点的完全图中拿掉一条曲线，它的最少交叉数就从3降到2；8个点时，从18降到15。