Erdős Problem #130
Editorial depth: Reviewed explanatory article — evidence qualified.
Snapshot classification: open (not automatically the live result).
Subject areas: graph theory, chromatic number.
Read this status correctly
The status above is reproduced from GCL's immutable external-catalogue snapshot. It is not a new claim of current mathematical resolution, a source-semantic review, an independent proof check, or GCL certification. A published proof and a GCL replay are separate events.
The question in plain language
Choose an infinite set \(A\) of distinct points in the Euclidean plane with no three collinear and no four lying on a common circle. Form a graph on \(A\): two vertices are adjacent precisely when their Euclidean distance is an integer.
Andrásfai and Erdős asked how large this graph's clique number and chromatic number can be. In particular, could it require infinitely many vertex colours? Integer distance means \(1,2,3,\ldots\) rather than an arbitrarily chosen real distance or a distance merely rational.
A small example
Three vertices of an equilateral triangle of integer side length form a triangle in the integer-distance graph; their points are noncollinear and automatically satisfy the condition excluding four concyclic points. Thus chromatic number three is possible. Four generic points might satisfy the incidence restrictions yet have no integer pairwise distances at all, showing why the induced graph must be calculated rather than assumed dense.
The graph is not the classical unit-distance graph: allowing all positive integer distances changes its edges and may raise chromatic number.
What is known
The main chromatic-number question remains OPEN. Anning and Erdős proved in Integral distances (1945) that an infinite planar set whose pairwise distances are all integers lies on a straight line. Consequently an infinite clique is impossible in this setting, because \(A\) contains no three collinear points.
That conclusion does not establish a universal finite bound on the sizes of cliques, nor does it establish finite chromatic number. Graphs can have unbounded chromatic number while every clique is small. The question asks about this separation under a stringent geometric incidence hypothesis.
The maintained Erdős #130 cites original [Er97b] and distinguishes the disproved possibility of an infinite clique from the unresolved chromatic-number question. Any new proof claim reported in the forum must be audited separately; its mere presence does not establish a consensus result.
GCL's current state
The pinned catalogue classifies #130 OPEN and records a formal statement. The original source issue is #1399. The Anning–Erdős theorem is attributed to the historical paper; its full original proof was not reconstructed in this source audit.
The original issue contains an authenticated RESULT/1 source report. This is unadjudicated source evidence only, not independent mathematical certification or editorial admission.
What remains
A bounded semantics fixture is to construct finite rational-coordinate point sets with no collinear triples and no concyclic quadruples, compute integer squared distances exactly using perfect-square tests, and independently calculate clique and chromatic numbers for examples of at most eight vertices. Acceptance: all geometric preconditions are checked first, and the triangle example gives chromatic number three. Stop at finite examples: neither infinity nor a uniform bound follows from them.
Sources and claim boundaries
- Anning and Erdős, Integral distances (1945), historic original theorem.
- Maintained Erdős #130, open question and clique distinction.
- Original GCL issue #1399.
No resolution of the infinite chromatic-number question, complete Anning–Erdős proof replay, or editorial admission is claimed.
Catalogue and evidence provenance
- Pinned catalogue source: teorth/erdosproblems at
536408716724. - GCL issue: #1399 — protected issue/assignment identity; its labels and results are live, not reproduced automatically here.
- GCL triage: FORMAL_SOURCE_REFRESH_REQUIRED.
- Formal-statement coverage: No statement was confirmed in GCL's pinned formal-provider snapshot. Presence does not mean the statement or proof has been checked.
- External mathematical status: consult current problem page and its dated bibliography.