Skip to content

Erdős Problem #1067

Editorial depth: Authored explanatory DRAFT — NOT editorially accepted.
Snapshot classification: disproved (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.

UNACCEPTED DRAFT — mathematical editorial review pending

This material is a provisional, source-qualified manuscript published for line-by-line scrutiny and real HTML/LaTeX testing. It has NOT received separate GCL editorial acceptance or independent mathematical certification. Its presence on this website is not evidence of a solution, reviewed coverage, or final publication.

Review the underlying draft on GitHub.

The question in plain language

The chromatic number of a graph is the smallest number of colours needed to colour its vertices without giving an edge's endpoints the same colour. For infinite graphs, it can be an infinite cardinal, such as \(\aleph_1\), the first uncountable cardinal.

A graph is infinitely vertex-connected when every pair of distinct vertices can be joined by infinitely many paths that have no internal vertices in common. Erdős Problem #1067 asked whether every graph of chromatic number \(\aleph_1\) contains an infinitely vertex-connected subgraph whose chromatic number is still \(\aleph_1\).

The distinction between having many paths and retaining uncountable chromatic number is central.

A small example

In the finite complete graph \(K_4\), each pair of vertices has three internally vertex-disjoint connecting paths: their direct edge and two length-two routes through the other vertices. But three paths are not infinitely many.

This illustrates what connectivity counts. A finite example can never establish or refute the uncountable-graph statement.

What is known

The original universal assertion is false. Komjáth obtained a consistency result in 2013. Soukup constructed a ZFC counterexample in 2015, and Bowler and Pitz published a simpler construction in 2024. These published mathematical results distinguish a counterexample available in ordinary set theory from a separate, vertex-cardinality-restricted formulation that has an independence phenomenon.

There is also an edge-connectivity variant, where one may remove finitely many edges rather than vertices. Thomassen studied a related negative version. Changing between vertex and edge connectivity changes the claim and must not be treated as a cosmetic notation difference.

GCL's current state

The authenticated source audit #2338 identifies Soukup's ZFC counterexample and the separate historical variants. The frozen formal-conjectures source records an external Lean proof reference and labels the main assertion false, but its local theorem uses an unproved placeholder.

The maintained catalogue labels #1067 disproved (Lean). That external label is not an assertion of independent GCL kernel replay or a new GCL proof.

What remains

The mathematical question in its original form is externally resolved. GCL must review the precise Soukup and Bowler–Pitz constructions, verify the original Erdős–Hajnal quantifiers, and independently replay the external Lean development before making a separate formal-certification claim. The neighboring open problem #1068 must not be declared resolved by the negative answer here.

Sources and claim boundaries

Catalogue and evidence provenance

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