Skip to content

Erdős Problem #595

Editorial depth: Reviewed explanatory article — evidence qualified.
Snapshot classification: open (not automatically the live result).
Subject areas: graph theory, set 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 is free of four-vertex cliques if it contains no complete subgraph on four vertices. Erdős #595 asks whether some infinite free of four-vertex cliques graph cannot have its edges covered by countably many triangle-free subgraphs. Equivalently, can one find such a graph for which every countable edge-colouring produces a monochromatic triangle? The question is existential: not every free of four-vertex cliques graph needs to have this property.

A small example

Every graph on a countable vertex set admits a countable covering by triangle-free graphs: list its vertices and put all edges at a vertex into its star. Stars contain no triangles.

In fact the same covering assertion holds whenever the vertex set has cardinality at most the continuum (the cardinality of all infinite binary sequences). Label each vertex by a distinct infinite binary sequence. Put an edge in class \(i\) where the endpoint sequences first differ at coordinate \(i\). Every class is bipartite, hence triangle-free, and the countably many classes cover all edges. The construction uses no free of four-vertex cliques assumption at all.

What is known

The continuum threshold is a classical edge-decomposition observation in the setting of Erdős–Hajnal's 1967 work. It means a hypothetical witness to #595 must have strictly more than continuum-many vertices. A disjoint union of finite graphs needing increasingly many colours can have countably infinite cover number and is not, by itself, a counterexample.

GCL's current state

The authenticated source audit reconciles the frozen statement, primary literature and bounded elementary checks. These observations are not a new GCL mathematical certification.

What remains

Produce a free of four-vertex cliques graph of cardinality larger than the continuum for which no countable triangle-free decomposition exists, or prove such graphs cannot occur. Finite Folkman-type obstructions do not automatically settle this much stronger infinite-cardinal question.

Sources and claim boundaries

  • Erdős Problems #595: reported statement and bibliographic status.
  • Erdős–Hajnal (1967), On decomposition of graphs, pp. 359–377, especially the historical cardinality threshold.
  • GCL source audit: elementary continuum construction, frozen theorem semantics, and protected predecessor limits.

Catalogue and evidence provenance

  • Pinned catalogue source: teorth/erdosproblems at 536408716724.
  • GCL issue: #1866 — protected issue/assignment identity; its labels and results are live, not reproduced automatically here.
  • GCL triage: FIRST_RECONNAISSANCE_TRANCHE.
  • Formal-statement coverage: A provider statement was included in the pinned 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