WorksMathematics
A counterexample to Erdős problem 1068
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.
Introduction
All graphs considered here are simple and undirected, and all paths are finite. For a graph and , write . A graph is connected when each pair of vertices is joined by a finite path. An infinite graph is infinitely vertex-connected if is connected for every finite .
Erdős problem 1068 asks whether every graph of chromatic number contains a countable infinitely vertex-connected subgraph [1]. We prove the following stronger negative statement.
Theorem 1.1. There is a graph such that
The path formulation of infinite connectivity leads to the same obstruction needed here. We record the implication explicitly.
Lemma 1.2. Suppose that has at least two vertices and that every two distinct vertices of are joined by infinitely many distinct simple paths with pairwise disjoint interiors. Then is infinite and is connected for every finite .
Proof. A finite graph has only finitely many simple paths between any fixed pair of vertices, so is infinite. Fix a finite set and distinct vertices . In a family of internally disjoint – paths, each vertex of lies on at most one path, since neither endpoint belongs to . Thus at most paths meet . A remaining path joins to in . □
Our construction and proof use only ZFC. We write , let be the first uncountable ordinal, and put .
The graph
Let
Thus an element of is a finite word whose letters belong to , and a node is a sequence of such words with countable ordinal length. Write for its length. Order by extension, denoted by . The empty sequence is the root. For finite words, and for their relation to an infinite sequence in , write for the initial-segment relation. If , then is an immediate successor of .
At each node place the vertex set
The sets are pairwise disjoint. Set
We call the cone above , and a child cone of . The word forms a single entry of the node . In particular, distinct words label disjoint child cones, including when one word is an initial segment of the other. We have the disjoint partition
Lemma 2.1. The sets , , and all have cardinality .
Proof. We have . For every countable ordinal ,
There are possible lengths. Hence and . Every has cardinality , so equality holds. Each cone contains a whole vertex set and is contained in , giving the remaining equalities. □
By the axiom of choice, fix, simultaneously for every and , a bijection
These maps are chosen from the already specified vertex sets. Define the graph on by the edge set
Here is the word consisting of the first entries of . Every displayed edge joins to a strict descendant of , so its endpoints are distinct.
Lemma 2.2. The graph has the following properties.
If an edge joins to , then and are distinct comparable nodes.
Distinct child cones of a node have no edges between them.
For , its neighbors in are precisely
Consequently, has at most one neighbor in each child cone of .
Proof. The first assertion follows from the range in (2) and the definition (3). Nodes in distinct child cones are incomparable, which proves the second assertion. If an edge from has its other endpoint at greater height, then is the lower endpoint in (3). This proves the displayed description of its upper neighbors. The words have distinct lengths and therefore label distinct child cones, proving the last assertion. □
The chromatic number
The function is a proper coloring by , by Lemma 2.2. Thus . To obtain equality, we show that every function assigns the same color to the endpoints of some edge.
For a fixed , put
Each is nonempty, and implies .
Lemma 3.1. There is a node such that
Proof. Starting with the root , construct nodes recursively. At stage , if there is an extension with , choose one and set . If there is no such extension, set . The nodes form an increasing sequence. Their union
is a node of , since its domain is the supremum of countably many countable ordinals and is therefore countable.
Let . Monotonicity gives . Conversely, suppose that . Color was not removed at stage , since removal would imply and hence . Therefore every extension of has color in its cone. As , we have . □
Proposition 3.2. The graph has chromatic number .
Proof. Suppose that is a proper coloring, and take as in Lemma 3.1. Choose a sequence whose range is . If this set is finite, repeat its elements.
We construct recursively. Once is known, (4) applied to gives a vertex with . Define
The resulting vertex belongs to , so . Choose with . By construction,
contradicting properness. Hence has no countable proper coloring. Together with the height coloring, this gives . □
Finite separators inside a cone
Fix and a nonempty word of length . Define
For , its external vertex boundary in is
Lemma 4.1. For the sets in (5) and (6),
Proof. For , the vertex lies in the child cone . Its label has length less than , so this cone is disjoint from every child cone whose label extends . It also misses . The labels are distinct, and therefore the displayed vertices are distinct. This proves the disjointness and cardinality claims.
Suppose that is adjacent to . First consider with . By Lemma 2.2,
for some . If , the word extends , putting in . Hence , and and . Thus .
It remains to consider for a word extending . The vertex lies outside this child cone. Distinct child cones have no edges between them, so the partition (1) implies that . Write . An edge from this vertex into requires for some , by Lemma 2.2. It follows that , placing in , a contradiction. This accounts for every possible boundary edge. □
Corollary 4.2. Any two distinct vertices of can be separated in by a finite vertex set that avoids both vertices.
Proof. Let and be distinct. Choose with , and set . Then
The set also avoids . By Lemma 4.1, no path in can leave , proving the assertion. □
Excluding infinitely connected subgraphs
Lemma 5.1. Let be nonempty, and suppose that is connected. If and is minimum among the heights of nodes whose vertex sets meet , then .
Proof. Choose . We show that every finite path in starting at stays in . Suppose that a vertex on the path lies in with , and the next vertex lies in . The nodes and are comparable, by Lemma 2.2. If , then . If , then and are both initial segments of . Minimality of gives , so again . Induction along the path proves the claim. Connectedness now gives . □
Proof of Theorem 1.1. Lemma 2.1 gives , and Proposition 3.2 gives .
Suppose, towards a contradiction, that is infinite and remains connected after every finite vertex deletion. Choose a node of minimum height with . Lemma 5.1 gives .
There is exactly one vertex of in . Indeed, if there were two, Corollary 4.2 would supply a finite separator avoiding both. Deleting from would still separate them, since every remaining path in is a path in . This contradicts the assumed connectivity. Write .
The graph is connected and infinite. Its vertices lie in the child cones of , by (1). Since distinct child cones have no edges between them, all of lies in a single child cone . Lemma 2.2 now shows that has at most one neighbor in .
Let be the set of neighbors of in . This set is finite and does not contain . In , the vertex is isolated, while infinitely many other vertices remain. Thus is disconnected, giving the final contradiction. □
Corollary 5.2. There is a graph of chromatic number with no infinitely vertex-connected subgraph. In particular, it has no countable subgraph of the kind required in Erdős problem 1068. The same conclusion holds for the path formulation on graphs with at least two vertices, requiring infinitely many internally vertex-disjoint paths between every two distinct vertices.
Proof. Let be the graph in Theorem 1.1. If a subgraph on an infinite vertex set remains connected after every finite deletion, then has the same property, since it contains every edge of . This contradicts the theorem. The path formulation implies the finite-deletion property by Lemma 1.2. □
Will Howe Email address: [email protected]
Grant Huffman Email address: [email protected]
Jensen Kohlmeyer Email address: [email protected]
Liam Kruer Email address: [email protected]
References
- [1]Erdős Problems, Problem 1068, https://www.erdosproblems.com/1068. Accessed November 11, 2026.