Skip to content

Erdős Problem #62

Editorial depth: Reviewed explanatory article — evidence qualified.
Snapshot classification: open (not automatically the live result).
Subject areas: graph theory.

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

A graph's chromatic number is the fewest colors needed to color its vertices without giving adjacent vertices the same color. Erdős asked whether any two graphs needing uncountably many colors must share some graph that needs four colors. The shared graph may be embedded separately into the two original graphs; the graphs do not need to have the same vertex set.

This remains an open problem. A related, weaker question about shared three-color graphs has a known affirmative answer.

A small example

An odd cycle, such as the five-cycle \(C_5\), needs exactly three colors. It cannot use only two, because alternating two colors around an odd number of edges ends with a conflict. Three suffice by alternating two colors along a path and using the third color at the last vertex.

If two graphs both contain a copy of \(C_5\), then they share a three-chromatic subgraph. But this says nothing about whether they share a graph of chromatic number four.

What is known

Erdős, Hajnal and Shelah proved in 1974 that every graph of chromatic number at least \(\aleph_1\) contains cycles of every sufficiently large odd length. The threshold may depend on the graph. Given two such graphs, choose an odd length larger than both thresholds. That same odd cycle embeds into each graph, and therefore the two graphs always have a common subgraph with chromatic number three.

The source is Erdős, Hajnal and Shelah, On some general properties of chromatic numbers, Topics in topology (1974), 243–255. The maintained catalogue also records this theorem under Erdős #594.

The remaining leap from three to four colors is substantial. Having every sufficiently large odd cycle is not enough to construct a common four-chromatic subgraph. The original question also asks about a common graph of countably infinite chromatic number.

GCL's current state

The pinned catalogue and maintained Erdős problem #62 classify the four-chromatic question as OPEN. The local editorial analysis verifies the logical consequence of the published odd-cycle theorem, without claiming a solution.

The original assignment is ERDOS-CATALOGUE-0062-S01. This is an unaccepted local draft. Theorem 3 on printed page 251 of the published 1974 paper was directly checked on 2026-10-13; its full proof was not independently re-proved.

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 task is to formalize the threshold statement for odd cycles and prove that two such thresholds can be combined into one common odd-cycle length. A separate elementary lemma establishes that odd cycles have chromatic number three. Neither lemma addresses the unresolved four-chromatic case.

The distinction between subgraph and induced subgraph is essential: the problem asks only for ordinary subgraph embeddings.

Sources and claim boundaries

No common four-chromatic construction, mathematical certification or editorial acceptance is claimed.

Catalogue and evidence provenance

  • Pinned catalogue source: teorth/erdosproblems at 536408716724.
  • GCL issue: #1331 — protected issue/assignment identity; its labels and results are live, not reproduced automatically here.
  • GCL triage: STATEMENT_CAPTURE_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.

Back to catalogue · Compendium introduction