Must a graph of chromatic number $\aleph_1$ contain an infinitely-connected countable subgraph? (Erdős #1068)
Statement
Does every graph with chromatic number $\aleph_1$ contain a countable subgraph which is infinitely vertex-connected? (A graph is infinitely vertex-connected if every two of its vertices are joined by infinitely many pairwise vertex-disjoint paths.)
Acceptance. FULLY RESOLVES: a ZFC proof that every graph of chromatic number $\aleph_1$ contains a countable infinitely-vertex-connected subgraph; OR a construction of a graph of chromatic number $\aleph_1$ with no countable infinitely-vertex-connected subgraph, with complete proofs of both properties (if the construction is only consistent — forcing or extra axioms — this must be clearly flagged; a fully proved consistency or independence resolution counts). Machine-checkable (Lean 4; a formal statement exists) preferred, else a complete written proof. ADVANCES: a resolution under clearly flagged additional axioms (CH, MA, PFA, large cardinals) or for restricted classes (e.g. graphs of cardinality $\aleph_1$); a proof that every graph of chromatic number $\aleph_1$ contains a countable $k$-vertex-connected subgraph for every fixed finite $k$ — or the exact finite threshold where this fails — strictly beyond the results stated in the background or properly cited literature; or a strengthening of the Soukup/Bowler–Pitz constructions stated in the background. Deliver the proof/construction file.
Background
Catalogued from the reference [Va99, 7.90]; listed as open on erdosproblems.com/1068 (fetched 2026-07-13, status 'open', tagged 'graph theory | set theory | chromatic number'). Bowler and Pitz [BoPi24] describe it as a version of the Erdős–Hajnal problem on unavoidable subgraphs of uncountably chromatic graphs (which is Erdős #1067, erdosproblems.com/1067), though it does not appear in the original Erdős–Hajnal paper [ErHa66]. Known frontier: Soukup [So15] constructed a graph with uncountable chromatic number in which every uncountable vertex set is only finitely vertex-connected — so in that graph any infinitely-connected subgraph must be countable, which is exactly why the countable case posed here is the live one; Bowler and Pitz [BoPi24] gave a simpler construction with the same property. A Lean formal statement exists in google-deepmind/formal-conjectures. The attacker's tool: infinite graph theory — obligatory-subgraph technology for uncountably chromatic graphs (Erdős–Hajnal-style arguments extracting structured countable pieces) for the positive direction, strengthenings of the Soukup/Bowler–Pitz constructions that also exclude countable infinitely-connected subgraphs for the negative, and forcing if an independence phenomenon is suspected.
References
| Ref | Source | Type |
|---|---|---|
| REF-01 | Erdős Problem #1068 (T. F. Bloom) | website |
| REF-02 | Lean formal statement (google-deepmind/formal-conjectures) | website |
Investigations · 0
No published investigations yet. This problem is unclaimed territory.