Skip to content

Erdős Problem #1068

Editorial depth: Authored explanatory DRAFT — NOT editorially accepted.
Snapshot classification: open (not automatically the live result).
Subject areas: graph theory, set 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.

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

An infinite graph can require uncountably many colours to colour its vertices properly. Erdős Problem #1068 asks:

Does every graph with chromatic number \(\aleph_1\) contain a countable subgraph that is infinitely vertex-connected?

Here, infinite vertex connectivity means any two vertices can be joined by infinitely many paths with pairwise disjoint interiors. Crucially, the countable subgraph does not need uncountable chromatic number. This makes #1068 different from Problem #1067, whose stronger conclusion was disproved.

A small example

Take the complete graph on an uncountable set of \(\aleph_1\) vertices. Its chromatic number is \(\aleph_1\), because each pair of vertices is adjacent.

Choose any countably infinite subset of vertices. The resulting induced subgraph is the complete countably infinite graph \(K_{\aleph_0}\). For any two distinct vertices \(u,v\), and for each other vertex \(w\), there is a path \(u-w-v\). Paths for distinct \(w\) share no interior vertices. Since there are infinitely many choices of \(w\), this countable subgraph is infinitely vertex-connected.

That is a positive example, not a proof about all graphs requiring \(\aleph_1\) colours.

What is known

The maintained catalogue records #1068 as open, specifically under the vertex-connectivity interpretation. Its historical references include a problem in Väänänen (1999), and work by Soukup, Bowler and Pitz on related uncountably chromatic graphs.

Soukup and Bowler–Pitz show that uncountably chromatic graphs need not contain uncountable infinitely vertex-connected subgraphs. Their negative result does not itself rule out the existence of a countable infinitely vertex-connected subgraph.

Infinite edge connectivity is also different: separating two vertices by deleting edges is not the same as separating them by deleting vertices. The site's January 2026 clarification explicitly makes the vertex interpretation the intended one.

GCL's current state

Authenticated source audit #2339 records the four combinations of countable versus uncountable subgraph and edge versus vertex connectivity, and verifies the elementary positive complete-graph example.

The frozen formal-conjectures file expresses the existence of a countable induced subgraph with infinite vertex connectivity. Its general theorem is unproved. No independent GCL formal certification is claimed.

What remains

The open problem requires either a proof for every uncountably chromatic graph or a counterexample. A useful source-bound next step is to examine Bowler–Pitz's actual construction and ask whether it has any countable infinitely vertex-connected induced subgraphs, while preserving the exact historical question and graph-theoretic definitions.

Sources and claim boundaries

Catalogue and evidence provenance

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