A counterexample to Erdős problem 1068
Version 1 / Nov 21, 2026 / CC BY 4.0
Abstract
We construct in ZFC a simple graph on vertices with chromatic number 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.
Provenance statement
References
- Erdős Problems , Problem 1068, https://www.erdosproblems.com/1068. Accessed November 11, 2026.link
Version history
- 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