betaFeedback

WorksMathematics

A counterexample to Erdős problem 1068

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.

Introduction

All graphs considered here are simple and undirected, and all paths are finite. For a graph HH and S⊆V(H)S \subseteq V(H), write H−S=H[V(H)∖S]H-S=H[V(H)\setminus S]. A graph is connected when each pair of vertices is joined by a finite path. An infinite graph HH is infinitely vertex-connected if H−SH-S is connected for every finite S⊆V(H)S\subseteq V(H).

Erdős problem 1068 asks whether every graph of chromatic number ℵ1\aleph_1 contains a countable infinitely vertex-connected subgraph [1]. We prove the following stronger negative statement.

Theorem 1.1. There is a graph GG such that

∣V(G)∣=2ℵ0,χ(G)=ℵ1,and, for every infinite W⊆V(G), there is a finite S⊆W for which G[W∖S] is disconnected.\begin{aligned} |V(G)| &= 2^{\aleph_0}, \qquad\chi(G)=\aleph_1,\\ &\text{and, for every infinite }W\subseteq V(G),\text{ there is a finite }S\subseteq W\text{ for which }G[W\setminus S]\text{ is disconnected.} \end{aligned}

The path formulation of infinite connectivity leads to the same obstruction needed here. We record the implication explicitly.

Lemma 1.2. Suppose that HH has at least two vertices and that every two distinct vertices of HH are joined by infinitely many distinct simple paths with pairwise disjoint interiors. Then HH is infinite and H−SH-S is connected for every finite S⊆V(H)S\subseteq V(H).

Proof. A finite graph has only finitely many simple paths between any fixed pair of vertices, so HH is infinite. Fix a finite set SS and distinct vertices u,v∈V(H)∖Su,v\in V(H)\setminus S. In a family of internally disjoint uu–vv paths, each vertex of SS lies on at most one path, since neither endpoint belongs to SS. Thus at most ∣S∣|S| paths meet SS. A remaining path joins uu to vv in H−SH-S. □

Our construction and proof use only ZFC. We write N={0,1,2,…}\mathbb{N}=\{0,1,2,\ldots\}, let ω1\omega_1 be the first uncountable ordinal, and put c=2ℵ0\mathfrak{c}=2^{\aleph_0}.

The graph

Let

A={0,1}N,L=A<ω=⋃n<ωAn,T=⋃α<ω1Lα.A=\{0,1\}^{\mathbb{N}},\qquad L=A^{<\omega}=\bigcup_{n<\omega}A^n,\qquad T=\bigcup_{\alpha<\omega_1}L^\alpha.

Thus an element of LL is a finite word whose letters belong to AA, and a node t∈Tt\in T is a sequence of such words with countable ordinal length. Write ht⁡(t)\operatorname{ht}(t) for its length. Order TT by extension, denoted by ⪯\preceq. The empty sequence is the root. For finite words, and for their relation to an infinite sequence in ANA^{\mathbb{N}}, write ⊑\sqsubseteq for the initial-segment relation. If s∈Ls\in L, then t⌢⟨s⟩t\mathbin{\smallfrown}\langle s\rangle is an immediate successor of tt.

At each node tt place the vertex set

Bt={(t,b):b∈AN}.B_t=\{(t,b):b\in A^{\mathbb{N}}\}.

The sets BtB_t are pairwise disjoint. Set

V=⋃˙t∈TBt,C(t)=⋃˙t⪯uBu,C(t,s)=C(t⌢⟨s⟩).V=\mathop{\dot\bigcup}_{t\in T}B_t,\qquad C(t)=\mathop{\dot\bigcup}_{t\preceq u}B_u,\qquad C(t,s)=C(t\mathbin{\smallfrown}\langle s\rangle).

We call C(t)C(t) the cone above tt, and C(t,s)C(t,s) a child cone of tt. The word ss forms a single entry of the node t⌢⟨s⟩t\mathbin{\smallfrown}\langle s\rangle. In particular, distinct words label disjoint child cones, including when one word is an initial segment of the other. We have the disjoint partition

C(t)=Bt∪˙⋃˙s∈LC(t,s).(1)C(t)=B_t\mathbin{\dot\cup}\mathop{\dot\bigcup}_{s\in L}C(t,s). \tag*{(1)}

Lemma 2.1. The sets VV, C(t)C(t), and C(t,s)C(t,s) all have cardinality c\mathfrak{c}.

Proof. We have ∣A∣=∣L∣=∣AN∣=c|A|=|L|=|A^{\mathbb{N}}|=\mathfrak{c}. For every countable ordinal α\alpha,

∣Lα∣≤cℵ0=(2ℵ0)ℵ0=c.|L^\alpha|\leq\mathfrak{c}^{\aleph_0}=(2^{\aleph_0})^{\aleph_0}=\mathfrak{c}.

There are ℵ1≤c\aleph_1\leq\mathfrak{c} possible lengths. Hence ∣T∣≤c|T|\leq\mathfrak{c} and ∣V∣≤c⋅c=c|V|\leq\mathfrak{c}\cdot\mathfrak{c}=\mathfrak{c}. Every BtB_t has cardinality c\mathfrak{c}, so equality holds. Each cone contains a whole vertex set BuB_u and is contained in VV, giving the remaining equalities. □

By the axiom of choice, fix, simultaneously for every t∈Tt\in T and s∈Ls\in L, a bijection

ϕt,s:A⟶C(t,s).(2)\phi_{t,s}:A\longrightarrow C(t,s). \tag*{(2)}

These maps are chosen from the already specified vertex sets. Define the graph GG on VV by the edge set

E(G)={{(t,b),ϕt,b↾n(b(n))}:t∈T, b∈AN, n∈N}.(3)E(G)=\left\{\left\{(t,b),\phi_{t,b\upharpoonright n}(b(n))\right\}:t\in T,\ b\in A^{\mathbb{N}},\ n\in\mathbb{N}\right\}. \tag*{(3)}

Here b↾nb\upharpoonright n is the word consisting of the first nn entries of bb. Every displayed edge joins BtB_t to a strict descendant of tt, so its endpoints are distinct.

Lemma 2.2. The graph GG has the following properties.

  1. If an edge joins BtB_t to BuB_u, then tt and uu are distinct comparable nodes.

  2. Distinct child cones of a node have no edges between them.

  3. For v=(t,b)v=(t,b), its neighbors in C(t)∖BtC(t)\setminus B_t are precisely

ϕt,b↾n(b(n)),n∈N.\phi_{t,b\upharpoonright n}(b(n)),\qquad n\in\mathbb{N}.

Consequently, vv has at most one neighbor in each child cone of tt.

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 (t,b)(t,b) has its other endpoint at greater height, then (t,b)(t,b) is the lower endpoint in (3). This proves the displayed description of its upper neighbors. The words b↾nb\upharpoonright n have distinct lengths and therefore label distinct child cones, proving the last assertion. □

The chromatic number

The function (t,b)↦ht⁡(t)(t,b) \mapsto\operatorname{ht}(t) is a proper coloring by ω1\omega_1, by Lemma 2.2. Thus χ(G)≤ℵ1\chi(G) \le\aleph_1. To obtain equality, we show that every function f:V→Nf: V \to\mathbb{N} assigns the same color to the endpoints of some edge.

For a fixed f:V→Nf: V \to\mathbb{N}, put

P(t)=f[C(t)]⊆N.P(t)=f[C(t)]\subseteq\mathbb{N}.

Each P(t)P(t) is nonempty, and t⪯ut \preceq u implies P(u)⊆P(t)P(u) \subseteq P(t).

Lemma 3.1. There is a node t∗∈Tt_* \in T such that

P(u)=P(t∗)for every u⪰t∗.(4)P(u)=P(t_*) \qquad\text{for every }u \succeq t_*. \tag*{(4)}

Proof. Starting with the root t0t_0, construct nodes tnt_n recursively. At stage nn, if there is an extension u⪰tnu \succeq t_n with n∉P(u)n \notin P(u), choose one and set tn+1=ut_{n+1}=u. If there is no such extension, set tn+1=tnt_{n+1}=t_n. The nodes form an increasing sequence. Their union

t∗=⋃n<ωtnt_*=\bigcup_{n<\omega}t_n

is a node of TT, since its domain is the supremum of countably many countable ordinals and is therefore countable.

Let u⪰t∗u \succeq t_*. Monotonicity gives P(u)⊆P(t∗)P(u) \subseteq P(t_*). Conversely, suppose that n∈P(t∗)n \in P(t_*). Color nn was not removed at stage nn, since removal would imply n∉P(tn+1)n \notin P(t_{n+1}) and hence n∉P(t∗)n \notin P(t_*). Therefore every extension of tnt_n has color nn in its cone. As u⪰t∗⪰tnu \succeq t_* \succeq t_n, we have n∈P(u)n \in P(u). □

Proposition 3.2. The graph GG has chromatic number ℵ1\aleph_1.

Proof. Suppose that f:V→Nf: V \to\mathbb{N} is a proper coloring, and take t∗t_* as in Lemma 3.1. Choose a sequence (kn)n∈N(k_n)_{n\in\mathbb{N}} whose range is P(t∗)P(t_*). If this set is finite, repeat its elements.

We construct b∈ANb \in A^{\mathbb{N}} recursively. Once b↾nb\mathbin{\upharpoonright} n is known, (4) applied to t∗⌢⟨b↾n⟩t_*^\frown\langle b\mathbin{\upharpoonright} n\rangle gives a vertex wn∈C(t∗,b↾n)w_n \in C(t_*,b\mathbin{\upharpoonright} n) with f(wn)=knf(w_n)=k_n. Define

b(n)=φt∗,b↾n−1(wn).b(n)=\varphi^{-1}_{t_*,b\mathbin{\upharpoonright} n}(w_n).

The resulting vertex v=(t∗,b)v=(t_*,b) belongs to C(t∗)C(t_*), so f(v)∈P(t∗)f(v)\in P(t_*). Choose mm with km=f(v)k_m=f(v). By construction,

{v,wm}∈E(G)andf(wm)=km=f(v),\{v,w_m\}\in E(G)\quad\text{and}\quad f(w_m)=k_m=f(v),

contradicting properness. Hence GG has no countable proper coloring. Together with the height coloring, this gives χ(G)=ℵ1\chi(G)=\aleph_1. □

Finite separators inside a cone

Fix t∈Tt\in T and a nonempty word p∈Lp\in L of length kk. Define

D(t,p)={(t,b):p⊑b}∪⋃s∈Lp⊑sC(t,s),(5)D(t,p)=\{(t,b):p\sqsubseteq b\}\cup\bigcup_{\substack{s\in L\\p\sqsubseteq s}}C(t,s), \tag*{(5)}
F(t,p)={φt,p↾j−1(p(j)):0≤j<k}.(6)F(t,p)=\{\varphi_{t,p\mathbin{\upharpoonright}j}^{-1}(p(j)):0\le j<k\}. \tag*{(6)}

For D⊆C(t)D\subseteq C(t), its external vertex boundary in G[C(t)]G[C(t)] is

∂C(t)D={y∈C(t)∖D: some x∈D is adjacent to y}.\partial_{C(t)}D=\{y\in C(t)\setminus D:\text{ some }x\in D\text{ is adjacent to }y\}.

Lemma 4.1. For the sets in (5) and (6),

∂C(t)D(t,p)⊆F(t,p),F(t,p)∩(D(t,p)∪Bt)=∅,∣F(t,p)∣=k.\partial C(t)D(t,p) \subseteq F(t,p), \qquad F(t,p) \cap\left(D(t,p) \cup B_t\right) = \varnothing, \qquad\lvert F(t,p)\rvert= k.

Proof. For j<kj < k, the vertex ϕt,p↾j(p(j))\phi_{t,p\restriction j}(p(j)) lies in the child cone C(t,p↾j)C(t,p\restriction j). Its label has length less than kk, so this cone is disjoint from every child cone whose label extends pp. It also misses BtB_t. The labels p↾jp\restriction j are distinct, and therefore the kk displayed vertices are distinct. This proves the disjointness and cardinality claims.

Suppose that x∈D(t,p)x \in D(t,p) is adjacent to y∈C(t)∖D(t,p)y \in C(t) \setminus D(t,p). First consider x=(t,b)x=(t,b) with p⊑bp \sqsubseteq b. By Lemma 2.2,

y=ϕt,b↾n(b(n))y=\phi_{t,b\restriction n}(b(n))

for some nn. If n≥kn \ge k, the word b↾nb\restriction n extends pp, putting yy in D(t,p)D(t,p). Hence n<kn < k, and b↾n=p↾nb\restriction n=p\restriction n and b(n)=p(n)b(n)=p(n). Thus y∈F(t,p)y \in F(t,p).

It remains to consider x∈C(t,s)x \in C(t,s) for a word ss extending pp. The vertex yy lies outside this child cone. Distinct child cones have no edges between them, so the partition (1) implies that y∈Bty \in B_t. Write y=(t,b)y=(t,b). An edge from this vertex into C(t,s)C(t,s) requires s=b↾ns=b\restriction n for some nn, by Lemma 2.2. It follows that p⊑s⊑bp \sqsubseteq s \sqsubseteq b, placing yy in D(t,p)D(t,p), a contradiction. This accounts for every possible boundary edge. □

Corollary 4.2. Any two distinct vertices of BtB_t can be separated in G[C(t)]G[C(t)] by a finite vertex set that avoids both vertices.

Proof. Let (t,b)(t,b) and (t,b′)(t,b') be distinct. Choose jj with b(j)≠b′(j)b(j) \ne b'(j), and set p=b↾(j+1)p=b\restriction(j+1). Then

(t,b)∈D(t,p),(t,b′)∉D(t,p)∪F(t,p).(t,b) \in D(t,p), \qquad(t,b') \notin D(t,p) \cup F(t,p).

The set F(t,p)F(t,p) also avoids (t,b)(t,b). By Lemma 4.1, no path in G[C(t)]−F(t,p)G[C(t)]-F(t,p) can leave D(t,p)D(t,p), proving the assertion. □

Excluding infinitely connected subgraphs

Lemma 5.1. Let W⊆VW \subseteq V be nonempty, and suppose that G[W]G[W] is connected. If Bt∩W≠∅B_t \cap W \ne\varnothing and ht⁡(t)\operatorname{ht}(t) is minimum among the heights of nodes whose vertex sets meet WW, then W⊆C(t)W \subseteq C(t).

Proof. Choose v∈Bt∩Wv \in B_t \cap W. We show that every finite path in G[W]G[W] starting at vv stays in C(t)C(t). Suppose that a vertex on the path lies in BuB_u with t⪯ut \preceq u, and the next vertex lies in BwB_w. The nodes uu and ww are comparable, by Lemma 2.2. If u⪯wu \preceq w, then t⪯wt \preceq w. If w⪯uw \preceq u, then ww and tt are both initial segments of uu. Minimality of ht⁡(t)\operatorname{ht}(t) gives ht⁡(w)≥ht⁡(t)\operatorname{ht}(w) \ge\operatorname{ht}(t), so again t⪯wt \preceq w. Induction along the path proves the claim. Connectedness now gives W⊆C(t)W \subseteq C(t). □

Proof of Theorem 1.1. Lemma 2.1 gives ∣V(G)∣=c\lvert V(G)\rvert= \mathfrak{c}, and Proposition 3.2 gives χ(G)=ℵ1\chi(G)=\aleph_1.

Suppose, towards a contradiction, that W⊆VW \subseteq V is infinite and H=G[W]H=G[W] remains connected after every finite vertex deletion. Choose a node tt of minimum height with Bt∩W≠∅B_t \cap W \ne\varnothing. Lemma 5.1 gives W⊆C(t)W \subseteq C(t).

There is exactly one vertex of WW in BtB_t. Indeed, if there were two, Corollary 4.2 would supply a finite separator F(t,p)F(t,p) avoiding both. Deleting F(t,p)∩WF(t,p) \cap W from HH would still separate them, since every remaining path in HH is a path in G[C(t)]−F(t,p)G[C(t)]-F(t,p). This contradicts the assumed connectivity. Write Bt∩W={v}B_t \cap W=\{v\}.

The graph H−{v}H-\{v\} is connected and infinite. Its vertices lie in the child cones of tt, by (1). Since distinct child cones have no edges between them, all of W∖{v}W\setminus\{v\} lies in a single child cone C(t,s)C(t,s). Lemma 2.2 now shows that vv has at most one neighbor in HH.

Let SS be the set of neighbors of vv in HH. This set is finite and does not contain vv. In H−SH-S, the vertex vv is isolated, while infinitely many other vertices remain. Thus H−SH-S is disconnected, giving the final contradiction. □

Corollary 5.2. There is a graph of chromatic number ℵ1\aleph_{1} 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 GG be the graph in Theorem 1.1. If a subgraph HH on an infinite vertex set WW remains connected after every finite deletion, then G[W]G[W] has the same property, since it contains every edge of HH. 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. [1]Erdős Problems, Problem 1068, https://www.erdosproblems.com/1068. Accessed November 11, 2026.

Paper details

vlnc:W_r94rzrsp
Version
v1 · latest
Published
Fresh — published within the last 30 days
License
CC BY 4.0
Usage

views · 10

downloads · 0

A view counts once per browser per day, a download each time the PDF is requested.

  • Mathematics

Not recorded for this paper

View statement
Looking for related papers…
Contents