Hadwiger–Nelson Problem: OpenAI’s Breakthrough Shows the Euclidean Plane Is Not Five-Colorable

A flat surface, a fixed distance, and a handful of colors. That sounds like an afternoon puzzle. Mathematicians have been wrestling with it since 1950.

The Hadwiger–Nelson Problem asks how many colors are needed to color every point in the plane so that points exactly one unit apart never share a color. OpenAI’s manuscript, The Euclidean plane is not five-colorable, reports a proof that five colors cannot work, even when the coloring is arbitrarily irregular.

The immediate consequence is precise: the answer must be six or seven, assuming the reported result holds. Seven colors already suffice. The paper does not establish that six do, so this is a stronger lower bound rather than a complete solution.

The interesting part goes beyond that extra color. The proof connects unrestricted colorings to measurable data, then uses geometry and topology to force a contradiction. Understanding that connection explains both the breakthrough and its limits.

1. The Hadwiger–Nelson Problem, Explained

Imagine an infinite sheet of paper covered with points. Give every point a color. Whenever two points are exactly one unit apart, their colors must differ.

“Exactly” matters. Two red points half a unit apart are allowed. Two red points two units apart are allowed. Only the forbidden distance triggers the rule, and the unit could be a centimeter or a meter because rescaling changes nothing essential.

Three corners of an equilateral triangle with unit-length sides need three different colors. Larger arrangements can create constraints that are harder to satisfy together.

Mathematically, connect every pair of points at distance one with an edge. The resulting infinite unit-distance graph turns the geometric question into graph coloring: what is the smallest number of labels that separates every connected pair?

2. From Four Colors to a Six-Color Lower Bound

Edward Nelson obtained the lower bound four in 1950. John Isbell found a seven-color construction, establishing the upper bound. The gap survived for decades.

The Moser spindle later supplied a small, memorable obstruction: seven points joined by unit-distance edges that cannot be colored with three colors.

In 2018, Aubrey de Grey raised the lower bound to five with a finite graph that was not four-colorable. His corrected construction had 1,581 vertices. Subsequent work reduced the size of such examples, including a 509-vertex graph by Jaan Parts.

This distinction keeps the headlines honest. A lower bound eliminates smaller answers. An upper bound supplies a working construction. A complete Hadwiger–Nelson Problem solution requires those bounds to meet.

3. What “The Euclidean Plane Is Not Five-Colorable” Proves

The manuscript is attributed to OpenAI and dated September 23, 2026. Its main theorem says that every five-coloring of the Euclidean plane contains two identically colored points exactly one unit apart.

In symbols, its conclusion is:

[ 6 \leq \chi(\mathbb{R}^{2}) \leq 7. ]

The left inequality is the new claim. The right comes from the classical construction.

The theorem imposes no regularity conditions on the color classes. A class is simply the set of points receiving one color. It need not consist of neat tiles, smooth patches, or even measurable sets.

That scope is essential. Showing that every tidy five-color pattern fails would still leave untidy patterns available. The unrestricted Hadwiger–Nelson Problem allows them all.

The paper works in ZFC, the standard set-theoretic framework including the axiom of choice. Readers don’t need its formal machinery to understand the statement, but that framework matters when passing between infinite graphs and finite obstructions.

4. Why the Four-Color Theorem Does Not Apply

The four-color theorem concerns maps, or equivalently planar graphs. Neighboring regions must receive different colors, and the associated graph can be drawn without crossing edges.

Here, distance determines the constraints. Two points become neighbors because they’re exactly one unit apart, regardless of which regions contain them. Edges in a unit-distance drawing can cross.

The crossings aren’t extra vertices. They don’t change which endpoints must have different colors. But the resulting graph need not be planar, so the four-color guarantee is unavailable.

Think of the difference as two coloring games played on the same tabletop. One checks shared borders. The other checks a ruler. The tabletop being flat doesn’t make their rules equivalent.

There is also a naming trap: Hadwiger’s graph-minor conjecture is a separate question relating chromatic number to complete graph minors. Similar names do not imply interchangeable results.

5. How Seven-Color Plane Coloring Works

The seven-color upper bound comes from a hexagonal tiling. Make each hexagon small enough that any two points inside it are less than one unit apart. Repeat seven colors so that different hexagons of the same color are sufficiently separated.

Same-colored points then fall into two safe categories: less than one unit apart within a tile, or more than one unit apart across separate tiles.

The paper gives a concrete choice of hexagons with circumradius 2/5. Their diameter is 4/5, so a single tile contains no unit-distance pair. Its seven-color lattice pattern also keeps points in distinct same-colored tiles more than one unit apart.

Boundary points need colors too. Assigning each boundary point to an incident hexagon preserves these strict distance margins. An illustration that quietly leaves all the borders uncolored would not prove anything about every point of the plane.

This construction explains why seven works. It doesn’t explain why six must fail. That remaining question requires a different construction or a stronger impossibility theorem.

6. The First Proof Idea: Recover Measurable Structure

Arbitrary colorings resist familiar geometric tools. If a color class isn’t measurable, asking how much area it occupies may have no ordinary answer. Yet area, averages, and density are useful ways to extract structure from a messy picture.

The OpenAI Hadwiger Nelson proof addresses that obstacle through a transfer theorem. For every finite number of colors, it claims an equivalence between the existence of a proper unrestricted coloring and a weak measurable coloring.

“Weak” carries real mathematical weight. Such a coloring permits exceptional bad pairs. Its requirement is that same-colored unit pairs have measure zero when position and direction are considered together, using plane area and angular measure on the unit circle.

This is not the assertion that every arbitrary coloring can simply be repainted into an ordinary measurable proper coloring. Nor is it enough to declare troublesome pairs “rare” and ignore them.

The construction starts on the countable algebraic plane, whose coordinates are real algebraic numbers. Averaging translations and rotations produces an invariant probability law on colorings. Spectral analysis separates a component compatible with ordinary continuous translations from a remaining component.

A central rigidity argument controls that remainder. The projection preserves nonnegative color weights, their total of one, and the correlations needed to prohibit unit-distance conflicts in the weak sense. These weights ultimately produce measurable labels on the plane.

For the converse, density points and finite-graph compactness recover unrestricted colorability. The equivalence creates a rigorous bridge into a setting where geometry can work, without assuming the original color classes were well behaved.

7. The Second Proof Idea: Make Five Labels Contradict Geometry

The measurable bridge is only half the job. Measurable sets can still have wildly complicated boundaries. The proof cannot assume a nice map with clean junctions.

Instead, it examines limiting color information around circles of radius close to one. At a center and direction, an angular “palette” records labels that retain positive weight in these limits.

The manuscript proves that almost every such palette has at most two labels at each fixed center. Relations between unit directions restrict which labels can occur together. Those restrictions turn the original coloring into structured local information.

Next comes topology. The proof tracks transitions between labels, smooths color indicators with disk averages, and constructs connected sets associated with pairs of labels. A topological obstruction forces a cycle involving three, four, or five labels.

Each cycle length fails differently:

• Five labels: the permitted angular patterns become incompatible.
• Four labels: antipodal directions lead to an impossible parity condition.
• Three labels: the restrictions leave an open region using only three labels almost everywhere.

The last case brings back the Moser spindle. The proof places its seven vertices within the restricted region, using a rational placement certificate. Combined with the density-point argument, its need for four colors contradicts the available three.

The crucial qualification is “almost everywhere.” A careless explanation would plant vertices on exceptional points and announce victory. The manuscript’s measure arguments are what let the finite obstruction do its work despite those exceptions.

That is the proof’s overall shape: recover measurable structure, extract connected constraints, and eliminate every possible label cycle.

8. Where Is the Finite Graph That Requires Six Colors?

De Grey’s breakthrough came with an explicit finite graph. Readers understandably expect the new six-color lower bound to come with another, perhaps larger, picture.

The paper does not display a finite graph witnessing the new bound. Instead, its theorem implies that one exists.

The de Bruijn–Erdős compactness theorem says that, for a fixed finite number of colors, a graph is colorable if every finite subgraph is colorable. Reversing that implication, failure of five-colorability for the whole plane guarantees a finite subgraph that also fails.

Existence is not construction. The argument doesn’t give a vertex count, coordinates, or a convenient instance to feed into a SAT solver. Finding an explicit obstruction would be valuable follow-up work.

The manuscript also derives a probabilistic consequence: under its stated invariant or periodic sampling conditions, five-colorings have a positive lower bound on the frequency of conflicts. The graph and resulting constant are existential, so this supplies no ready numerical benchmark for an experiment.

9. What the Hadwiger Nelson Lean Proof Establishes

OpenAI’s formalization scope document says the associated Lean results cover both the impossibility of a proper five-coloring and the existence of a proper seven-coloring. The lower-bound statement includes arbitrary color classes, while the upper bound includes tile boundaries.

That scope matches the substantive question. A result restricted to smooth patches or measurable proper colorings would require different wording.

There is a practical trap in the repository: a comparator challenge states the target theorem, rather than serving as its completed proof. The five-color challenge contains a sorry placeholder. Finding that file alone establishes neither successful verification nor a flaw in the separate proof implementation.

Proper checking requires the supporting implementation and comparison setup. Reviewers must verify that the exported result matches the intended statement and that its assumptions are acceptable. This article does not claim an independent execution of that verification pipeline.

Formal checking and mathematical review also answer different questions. Lean checks logical derivation within a formal environment. Expert review assesses the correspondence with the paper, explains the ideas, and places the contribution in the literature.

The Hadwiger–Nelson Problem remains a research question even when one proposed answer has machine-checkable support. A proof artifact deserves attention, and its exact coverage deserves equal attention.

10. Why Earlier Six-Colorings Did Not Settle the Question

Search for this topic and you’ll encounter research describing six-colorings of the plane. That can sound inconsistent with an unresolved six-versus-seven choice.

The prominent work by Konrad Mundinger, Sebastian Pokutta, Christoph Spiegel, and Max Zimmer studies a modified rule. Five colors avoid monochromatic pairs at distance one. The sixth avoids monochromatic pairs at another specified distance.

Their machine-learning-assisted constructions expand the available range of that other distance. They do not establish a proper six-coloring in which every color avoids distance one.

The distinction is small in a headline and decisive in a theorem. If the sixth color follows a different rule, it cannot serve as the missing upper bound for the original problem.

Related research on other norms changes the geometry itself. The Euclidean plane in the Hadwiger–Nelson Problem uses ordinary straight-line distance. Changing the distance rule creates an interesting neighboring question, rather than answering this one.

11. What This Says About AI Mathematical Discovery

OpenAI attributes the collection to an unreleased internal model. Its repository reports an average of three hours of ChatGPT Pro thinking compute per result, across an evaluation involving approximately 4,000 problems.

That average is not a published stopwatch reading for this manuscript. It doesn’t disclose this result’s token count, hardware allocation, or full sequence of attempts. Social-media accounts of unsuccessful earlier searches cannot fill those gaps or establish a controlled comparison between models.

The stronger evidence of capability would be a correct theorem supported by a useful new argument. Here, the transfer theorem is especially interesting because its statement applies to every finite number of colors, while the geometric contradiction specifically uses five.

That separation suggests a tool other researchers could study independently of this particular bound. It is a plausible research opportunity, not a promise that the same machinery automatically resolves six colors or other famous conjectures.

For developers building mathematical agents, the lesson is practical: candidate generation, formal checking, and understandable exposition are distinct jobs. A system can produce a compelling manuscript without making every verification and interpretation step disappear.

12. The Remaining Color Is the Next Question

The Hadwiger–Nelson Problem now has a reported improvement from a five-color lower bound to six. The exact answer still needs either a proper six-color construction or a proof that six also fails.

For readers following the work, the useful next steps are concrete: examine the formalization scope, watch for independent checking, and look for an explicit finite obstruction. Each would add something different to our understanding.

OpenAI’s contribution is most compelling when described precisely: an unrestricted lower-bound improvement built on a bridge between arbitrary labels and measurable geometry. That is substantial enough without calling the whole problem solved.

Follow Binary Verse AI at binaryverseai.com for research explainers that unpack the theorem, the evidence, and the next unresolved question. The best way to follow AI mathematics is to understand what each result actually earns.