JOIN EVERY DOT TO EVERY OTHER: THE FEWEST CROSSINGS, PROVED

Put five dots on a sheet of paper and join every pair with a curve: ten curves in all. They may bend as you like, but none may run through a third dot. Try to avoid every crossing, and you will fail. With five dots, at least 1 crossing is unavoidable; with six, at least 3; with ten, at least 60.

Mathematicians call such a picture a drawing of the complete graph Kₙ — n points, every pair joined — and the fewest crossings any drawing can reach its crossing number. Martin Balko, of Charles University in the Czech Republic, calls the question “one of the most famous problems in topological graph theory”.

An artist’s count

In the late 1950s, the British artist Anthony Hill constructed drawings of Kₙ with exactly

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

crossings, where ⌊ ⌋ means rounding down. The guess that no drawing can do better was first published by Guy, later discussed by Harary and Hill, and popularised by Erdős and Guy. It is known as the Harary–Hill conjecture, or Guy’s conjecture.

The formula climbs quickly:

• 4 dots or fewer: 0 crossings
• 5 dots: 1
• 7 dots: 9
• 10 dots: 60
• 14 dots: 315

Six decades of partial answers

Drawings with exactly Z(n) crossings existed for every number of dots; the hard part was showing that no drawing does better.

For more than sixty years, that was proved only for special kinds of drawings — for instance with all the dots on one line and each curve kept on one side of it, or with the dots on a sphere and each curve taking the shortest route. Balko himself, with Fulek and Kynčl, had settled one such class. By 2021, computers had confirmed the formula up to 14 dots. For very large numbers of dots, the best general results guaranteed at least 98.5%, then 98.99%, of Z(n).

A proof, then a clearer one

In 2026, OpenAI announced a proof for every number of dots, which Balko’s paper lists as an “OpenAI Math Release preprint” and credits with the theorem. The paper does not say how that proof was found. In Balko’s words, the original “is relatively short”, but “quite difficult to follow”. His preprint presents a streamlined variant which, he writes, “requires only elementary knowledge of linear algebra and graph theory”. Another mathematician, Gelasio Salazar, is preparing a separate, detailed exposition.

Counting coefficients instead of crossings

Since known drawings already reach Z(n), only the lower bound needs proof. It takes four moves.

1. Odd numbers suffice. A best drawing can be redrawn so that curves sharing a dot never cross; each crossing then involves 4 different dots. Delete each of 6 dots in turn: every leftover 5-dot picture has at least 1 crossing, and each crossing survives exactly 2 of the 6 deletions (it vanishes whenever one of its own 4 dots is deleted, and survives the other 2). So twice the crossings is at least 6: at least 3, which is Z(6). The same count works for every even number.
2. A family of polynomials. Give each dot its own number. A crossing involves two curves, so four dots, so four numbers. Balko uses polynomials in four variables, chosen so that the family has exactly Z(n) independent coefficients when n is odd — for 7 dots, 3 × 3 = 9.
3. Too few crossings leave room. Asking a polynomial to vanish at a crossing is one equation. With fewer equations than free coefficients, linear algebra always leaves a non-zero solution. So a drawing with fewer than Z(n) crossings would come with a non-zero polynomial vanishing at all its crossings; take the one of lowest degree.
4. The plane pushes back. Geometry enters through one classical fact: a closed loop in the plane crosses another from right to left exactly as often as from left to right. With well-chosen weights, this yields a sum of squares of the polynomial’s values, some counted positively, some negatively, that totals zero. The positive terms all sit at crossings, where the polynomial is zero, so the negative ones must vanish too. A second use of the loop fact makes it divisible by a fixed factor; dividing gives a non-zero polynomial of lower degree with the same property, which is impossible, since we took the lowest.

That sign argument is Balko’s main change: it replaces the original argument “involving a nondegenerate bilinear form and orthogonal complements”. He also proves the loop fact differently and isolates each dot more directly.

Other networks settled at once

The answer stays Z(n) if one counts, instead of crossings, the pairs of curves that cross at all, or that cross an odd number of times — as long as curves sharing a dot never meet elsewhere. Combined with earlier reductions, the theorem also gives exact crossing numbers for complete graphs with some links removed, for copies of a complete graph chained along a path or around an even cycle, and for a family of fractal-like networks called extended Sierpiński graphs.

Take away a single curve from the complete graph on 6 dots, and its minimum drops from 3 crossings to 2; on 8 dots, from 18 to 15.