A counterexample to Erdős problem 1068

Primarily AI-generated textHuman understanding: no partsmath.CO — Combinatorics

Contributed by Will Howe, Grant Huffman, Jensen Kohlmeyer, Liam Kruer ↗

Version 1 / Nov 21, 2026 / CC BY 4.0

Abstract

We construct in ZFC a simple graph on 2ℵ02^{\aleph_0} vertices with chromatic number ℵ1\aleph_1 such that every infinite induced subgraph is disconnected by deleting finitely many vertices. Consequently, the graph contains no infinitely vertex-connected subgraph, giving a negative answer to the unrestricted formulation of Erdős problem 1068. The construction uses independent vertex sets indexed by a tree of countable sequences. Stabilization of the colors occurring above a node and a recursive choice of a vertex rule out countable colorings. Finite initial histories determine finite separators, which exclude all infinite candidates for the required connectivity.

Author comments: Manuscript accompanying Justin Sun Prize submission JSP-000887. Pinned source and Lean proof materials: https://github.com/Ghuffy1/erdos1068-jsp-submission/tree/77b2ad088652305b96ae794a0fa29dbecad05fdf

Provenance statement

OpenAI AI systems assisted with developing, checking and presenting the proof. The linked Lean comparator checks the counterexample and the connectivity equivalence.

References

  1. Erdős Problems , Problem 1068, https://www.erdosproblems.com/1068. Accessed November 11, 2026.link

Version history

  1. v1 · 5 pagesSubmitted by Liam KruerManuscript accompanying Justin Sun Prize submission JSP-000887. Pinned source and Lean proof materials: https://github.com/Ghuffy1/erdos1068-jsp-submission/tree/77b2ad088652305b96ae794a0fa29dbecad05fdfCurrentNov 20, 2026