In September 2026, two OpenAI preprints (OpenAI 2026b, 2026a) announced proofs of two classical conjectures in graph theory: the Harary–Hill conjecture and Zarankiewicz’s conjecture. Both concern a question that is very easy to formulate: how many crossings are unavoidable when we draw a graph in the plane?
Let us recall some definitions.
A graph consists of a set of vertices, some pairs of which are joined by edges. To draw a graph in the plane, we represent its vertices by distinct points and its edges by curves joining the corresponding endpoints.
The curves are not required to be straight lines. However, an edge cannot pass through a vertex other than its endpoints, and we assume that crossings are ordinary transverse intersections, with no three edges crossing at the same point.
The crossing number of a graph , denoted by , is the smallest possible number of crossings among all such drawings of .
For example, a triangle can be drawn without crossings, so its crossing number is zero. The same is true for any graph that can be drawn in the plane without crossing edges. Such graphs are called planar.
But not every graph is planar. In particular, the complete graph , consisting of five vertices with every pair joined by an edge, cannot be drawn without crossings. In fact,
More generally, let denote the complete graph on vertices. Since it has edges, the problem of determining its crossing number becomes increasingly complicated as grows.
In 1963, Harary and Hill (Harary and Hill 1963) formulated a conjecture predicting an exact formula for . Their formula was based on an ingenious drawing in which all vertices lie on a line, and each edge is drawn on one of the two sides of that line.
This construction gave an upper bound, but proving that no other drawing could have fewer crossings turned out to be extremely difficult.
The conjecture was verified for a number of small values of . For example, computer-assisted arguments eventually established Nevertheless, the general formula remained unproved.
A closely related problem concerns complete bipartite graphs. The graph consists of two disjoint sets of vertices, containing and vertices respectively, with every vertex in one set joined to every vertex in the other set, but no edges joining vertices in the same set.
The simplest nonplanar example is , for which
This problem has an interesting history. In 1944, while working at a brick factory near Budapest, Paul Turán considered the problem of connecting several brick kilns to several storage yards by railway tracks while minimizing the number of crossings.
Mathematically, this is exactly the problem of determining .
In 1955, Zarankiewicz (Zarankiewicz 1955) published a formula for this crossing number. Unfortunately, his argument for the lower bound contained a gap. The formula remained a conjecture, although it was subsequently proved in many special cases.
The two new preprints claim to settle both problems in full.
The first formula is precisely the Harary–Hill conjecture, while the second is Zarankiewicz’s conjecture.
For example, the first formula gives
Similarly, the second formula gives
For large values of , the formulas imply where means that tends to as .
Thus, although both graphs have only a quadratic number of edges, their minimum number of crossings grows as the fourth power of the number of vertices.
Let us explain why establishing these formulas is difficult.
It is relatively easy to construct drawings attaining the displayed numbers of crossings. For complete bipartite graphs, for example, place the vertices of one class on a vertical line, divided as evenly as possible above and below the origin. Place the vertices of the other class on a horizontal line, divided similarly to the left and right of the origin, and join every required pair by a straight segment.
By counting the crossings in each of the four quadrants, we obtain exactly crossings, after choosing the vertex positions to avoid triple crossings.
This proves that the crossing number cannot exceed the conjectured value.
But how do we prove that every other possible drawing must have at least this many crossings? The edges of a graph may be represented by extremely complicated curves, and there are infinitely many possible ways to draw them.
The main achievement of the new papers is to establish this lower bound without imposing restrictions on the drawing.
The authors use a combination of topology, polynomial interpolation, and linear algebra.
The starting point is to assign a sign to every crossing between two directed edges. The sign depends on the relative orientations of the two curves at their intersection.
A classical fact from topology says that the total signed number of intersections of two closed curves in the plane is zero. The authors modify this identity to account for the cyclic order of edges around each vertex.
This produces algebraic relations among the crossings that must hold in every drawing.
The next step is particularly clever. Using polynomial interpolation, the authors convert these relations into statements about the ranks of certain matrices. The matrices are constructed so that some of them necessarily have large rank, while the ranks of others are bounded by the numbers of crossings between corresponding groups of edges.
An inequality from linear algebra then forces the total number of crossings to be at least the conjectured value.
For complete bipartite graphs, the authors first establish the lower bound when one of the vertex classes has odd size. The even case then follows by a counting argument in which vertices are deleted one at a time.
The proof for complete graphs uses related ideas, but with a different polynomial interpolation argument. Again, the essential step is to translate geometric information about crossings into algebraic inequalities that hold for every possible drawing.
The Harary–Hill argument has already inspired a detailed exposition by Salazar (Salazar 2026), who also extends the approach to more general combinatorial structures describing the cyclic orders of edges at vertices.
The two OpenAI papers are currently preprints, and their claims are subject to independent mathematical scrutiny. If the proofs are confirmed, they will settle two of the most famous problems in topological graph theory, one dating back more than sixty years and the other connected with Turán’s question from the 1940s.
What makes the result especially satisfying is that the optimal drawings have been known for decades. The difficult question was not how to draw the graphs with relatively few crossings, but how to prove that no more ingenious arrangement of curved edges could do better.
The new theorem claims that the classical constructions were optimal all along.