Conjectura
Beta.Proofs cannot be submitted yet. The corpus is open to read, and we are looking for researchers to maintain a subject area.Maintaining a field →
← problemsGT001openMathematics/ Combinatorics/ Graph theory

How many colours does the plane need?

Maintainer — open

Colour every point of the plane so no two points exactly one unit apart share a colour. Five is not enough; seven suffice. Is six?

Motivation

The Hadwiger–Nelson problem, posed in 1950.

The answer sat between 4 and 7 for 68 years. In 2018 Aubrey de Grey, an amateur in this field, exhibited a unit-distance graph with chromatic number 5, raising the lower bound; the upper bound of 7 comes from a hexagonal tiling. Whether 6 suffices is open.

The de Grey construction is a good argument for this project: it was found by computer search, verified by others by computer, and would have been a natural thing to check mechanically.

Edward Nelson, 1950. Lower bound 5: de Grey 2018.

Lean API
import Conjectura.Defs.Mathematics.Combinatorics.GraphTheory.UnitDistanceGraph
import Mathlib.Analysis.InnerProductSpace.EuclideanDist
import Mathlib.Combinatorics.SimpleGraph.Coloring.Vertex

namespace Conjectura.GT001

/-- How many colours are needed so that no two points of the plane at distance one
share a colour? De Grey showed in 2018 that five is not enough; seven suffice. Six
remains undecided, which is what this asks. -/
def goal : Prop :=
  (Conjectura.GraphTheory.unitDistanceGraph (EuclideanSpace ℝ (Fin 2))).Colorable 6

end Conjectura.GT001
Definition6
unit-distance graphConjectura.GraphTheory.unitDistanceGraph

The unit-distance graph on a metric space joins two points exactly when they are at distance one. Over the Euclidean plane, its chromatic number is the Hadwiger–Nelson problem.

def unitDistanceGraph (X : Type*) [MetricSpace X] : SimpleGraph X where
  Adj x y := x ≠ y ∧ dist x y = 1
  symm := ⟨fun _ _ h => ⟨h.1.symm, by rw [dist_comm]; exact h.2⟩⟩
  loopless := ⟨fun _ h => h.1 rfl⟩
MetricSpaceMetricSpace

class

AdjAdj

structure

symmh.1.symm

def

EuclideanSpaceEuclideanSpace

abbrev

ColorableColorable

def

Related work1
For your AI
Download as .md
I am proving a theorem in Lean 4 and submitting it to Conjectura.

## Problem GT001 — How many colours does the plane need?

Colour every point of the plane so no two points exactly one unit apart share a colour. Five is not enough; seven suffice. Is six?

## Environment (fixed — do not assume anything newer)

- Lean toolchain: `leanprover/lean4:v4.33.0-rc1`
- Mathlib: `v4.33.0-rc1`

If a lemma you want does not exist in that Mathlib, prove it inline instead of
importing something newer.

## The exact statement I must prove

```lean
theorem solution : (unitDistanceGraph (EuclideanSpace ℝ (Fin 2))).Colorable 6 := by
  sorry
```

## The file I submit

```lean
import Conjectura.Problems.GT001.Statement

namespace Submission

theorem solution : Conjectura.GT001.goal := by
  sorry

end Submission

```

## The Lean definitions of every term in this problem

These are the actual definitions your proof will be checked against. Do not
substitute your own version of any of them.

### unit-distance graph

The unit-distance graph on a metric space joins two points exactly when they are at distance one. Over the Euclidean plane, its chromatic number is the Hadwiger–Nelson problem.

```lean
Conjectura.GraphTheory.unitDistanceGraph
-- unfolds to:
def unitDistanceGraph (X : Type*) [MetricSpace X] : SimpleGraph X where
  Adj x y := x ≠ y ∧ dist x y = 1
  symm := ⟨fun _ _ h => ⟨h.1.symm, by rw [dist_comm]; exact h.2⟩⟩
  loopless := ⟨fun _ h => h.1 rfl⟩
```
Defined in this corpus.

### MetricSpace

class

```lean
MetricSpace
```
Defined in Mathlib.

### Adj

structure

```lean
Adj
```
Defined in Mathlib.

### symm

def

```lean
h.1.symm
```
Defined in Mathlib.

### EuclideanSpace

abbrev

```lean
EuclideanSpace
```
Defined in Mathlib.

### Colorable

def

```lean
Colorable
```
Defined in Mathlib.

## Rules — submissions violating these are rejected automatically

1. **Do not change the name or type of `solution`.** It must satisfy the
   statement above exactly.
2. **Do not redefine or shadow anything from the problem's Statement module.**
   Declaring your own `goal`, or redefining a name it depends on, produces a
   proof of a *different* statement and is rejected. This is the single most
   common rejection.
3. **No `sorry`** anywhere, including in helper lemmas. It surfaces as the
   axiom `sorryAx` and is detected transitively through imports.
4. **No `native_decide`** — it surfaces as `Lean.ofReduceBool` and is not
   accepted, because it trusts compiled code rather than the kernel.
5. Only these axioms are permitted: `propext`, `Classical.choice`,
   `Quot.sound`.
6. Follow Mathlib style: hypotheses left of the colon, explicit types,
   `snake_case` theorem names, `UpperCamelCase` types.

## What I want from you

Here is my argument in informal mathematics:

> [PASTE YOUR PROOF SKETCH HERE]

Turn it into Lean 4 that compiles under the environment above and satisfies the
statement exactly. Where you are unsure a lemma exists in this Mathlib version,
say so explicitly rather than guessing a name.

Submissions are not open yet

Conjectura is in beta. You can read every statement, every definition and the Lean behind them, and download the exact files the checker uses — but proofs are not being accepted yet.

The reason is a deliberate order of operations. Accepting a proof means running a stranger’s code and standing behind a verdict, and no statement here yet carries a researcher’s name. A machine-checked answer to a question nobody has vouched for is worth very little, so the vouching comes first.

The English write-ups are also switched off during the beta. Nothing on this page is generated by a model.

Discussion

  • Nothing yet.

Sign in to take part.