\documentclass[11pt,reqno]{amsart} \usepackage[letterpaper,margin=1in]{geometry} \usepackage[T1]{fontenc} \usepackage{lmodern} \usepackage{amsmath,amssymb,amsthm,mathtools} \usepackage{microtype} \usepackage[hidelinks]{hyperref} \hypersetup{ pdftitle={A Counterexample to Erdos Problem 1068}, pdfauthor={Will Howe, Grant Huffman, Jensen Kohlmeyer, Liam Kruer}, pdfsubject={Infinite graphs, chromatic number, and vertex connectivity}, pdfkeywords={Erdos problem 1068, infinite graph, chromatic number, finite separator} } \newtheorem{theorem}{Theorem}[section] \newtheorem{lemma}[theorem]{Lemma} \newtheorem{proposition}[theorem]{Proposition} \newtheorem{corollary}[theorem]{Corollary} \theoremstyle{definition} \newtheorem{definition}[theorem]{Definition} \newcommand{\N}{\mathbb N} \newcommand{\cont}{\mathfrak c} \newcommand{\height}{\operatorname{ht}} \newcommand{\res}{\mathbin{\upharpoonright}} \newcommand{\fcat}{\mathbin{{}^\frown}} \title[A counterexample to Erd\H{o}s problem 1068]{A counterexample to Erd\H{o}s problem 1068} \author[W. Howe, G. Huffman, J. Kohlmeyer, and L. Kruer]{Will Howe, Grant Huffman, Jensen Kohlmeyer, and Liam Kruer} \date{November 11, 2026} \subjclass[2020]{05C15, 05C40} \keywords{Infinite graph, chromatic number, vertex connectivity, finite separator} \thanks{All four authors contributed equally. The authors acknowledge assistance from OpenAI's AI systems in the development, checking, and exposition of the proof.} \begin{document} \begin{abstract} We construct in ZFC a simple graph on $2^{\aleph_0}$ vertices with chromatic number $\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\H{o}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. \end{abstract} \maketitle \raggedbottom \section{Introduction} All graphs considered here are simple and undirected, and all paths are finite. For a graph $H$ and $S\subseteq V(H)$, write $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 $H$ is \emph{infinitely vertex-connected} if $H-S$ is connected for every finite $S\subseteq V(H)$. Erd\H{o}s problem 1068 asks whether every graph of chromatic number $\aleph_1$ contains a countable infinitely vertex-connected subgraph \cite{erdos1068}. We prove the following stronger negative statement. \begin{theorem}\label{thm:main} There is a graph $G$ such that \[ |V(G)|=2^{\aleph_0},\qquad \chi(G)=\aleph_1, \] and, for every infinite $W\subseteq V(G)$, there is a finite $S\subseteq W$ for which $G[W\setminus S]$ is disconnected. \end{theorem} The path formulation of infinite connectivity leads to the same obstruction needed here. We record the implication explicitly. \begin{lemma}\label{lem:paths} Suppose that $H$ has at least two vertices and that every two distinct vertices of $H$ are joined by infinitely many distinct simple paths with pairwise disjoint interiors. Then $H$ is infinite and $H-S$ is connected for every finite $S\subseteq V(H)$. \end{lemma} \begin{proof} A finite graph has only finitely many simple paths between any fixed pair of vertices, so $H$ is infinite. Fix a finite set $S$ and distinct vertices $u,v\in V(H)\setminus S$. In a family of internally disjoint $u$--$v$ paths, each vertex of $S$ lies on at most one path, since neither endpoint belongs to $S$. Thus at most $|S|$ paths meet $S$. A remaining path joins $u$ to $v$ in $H-S$. \end{proof} Our construction and proof use only ZFC. We write $\N=\{0,1,2,\ldots\}$, let $\omega_1$ be the first uncountable ordinal, and put $\cont=2^{\aleph_0}$. \section{The graph} Let \[ A=\{0,1\}^{\N},\qquad L=A^{<\omega}=\bigcup_{n<\omega}A^n,\qquad T=\bigcup_{\alpha<\omega_1}L^\alpha. \] Thus an element of $L$ is a finite word whose letters belong to $A$, and a node $t\in T$ is a sequence of such words with countable ordinal length. Write $\height(t)$ for its length. Order $T$ by extension, denoted by $\preceq$. The empty sequence is the root. For finite words, and for their relation to an infinite sequence in $A^{\N}$, write $\sqsubseteq$ for the initial-segment relation. If $s\in L$, then $t\fcat\langle s\rangle$ is an immediate successor of $t$. At each node $t$ place the vertex set \[ B_t=\{(t,b):b\in A^{\N}\}. \] The sets $B_t$ are pairwise disjoint. Set \[ V=\bigcup_{t\in T}B_t, \qquad C(t)=\bigcup_{t\preceq u}B_u, \qquad C(t,s)=C\bigl(t\fcat\langle s\rangle\bigr). \] We call $C(t)$ the cone above $t$, and $C(t,s)$ a child cone of $t$. The word $s$ forms a single entry of the node $t\fcat\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 \begin{equation}\label{eq:partition} C(t)=B_t\ \dot\cup\ \mathop{\dot\bigcup}_{s\in L}C(t,s). \end{equation} \begin{lemma}\label{lem:cardinality} The sets $V$, $C(t)$, and $C(t,s)$ all have cardinality $\cont$. \end{lemma} \begin{proof} We have $|A|=|L|=|A^{\N}|=\cont$. For every countable ordinal $\alpha$, \[ |L^\alpha|\leq \cont^{\aleph_0} =\bigl(2^{\aleph_0}\bigr)^{\aleph_0}=\cont. \] There are $\aleph_1\leq\cont$ possible lengths. Hence $|T|\leq\cont$ and $|V|\leq\cont\cdot\cont=\cont$. Every $B_t$ has cardinality $\cont$, so equality holds. Each cone contains a whole vertex set $B_u$ and is contained in $V$, giving the remaining equalities. \end{proof} By the axiom of choice, fix, simultaneously for every $t\in T$ and $s\in L$, a bijection \begin{equation}\label{eq:phi} \phi_{t,s}:A\longrightarrow C(t,s). \end{equation} These maps are chosen from the already specified vertex sets. Define the graph $G$ on $V$ by the edge set \begin{equation}\label{eq:edges} E(G)= \left\{ \left\{(t,b),\phi_{t,b\res n}\bigl(b(n)\bigr)\right\} :t\in T,\ b\in A^{\N},\ n\in\N \right\}. \end{equation} Here $b\res n$ is the word consisting of the first $n$ entries of $b$. Every displayed edge joins $B_t$ to a strict descendant of $t$, so its endpoints are distinct. \begin{lemma}\label{lem:incidence} The graph $G$ has the following properties. \begin{enumerate} \item If an edge joins $B_t$ to $B_u$, then $t$ and $u$ are distinct comparable nodes. \item Distinct child cones of a node have no edges between them. \item For $v=(t,b)$, its neighbors in $C(t)\setminus B_t$ are precisely \[ \phi_{t,b\res n}\bigl(b(n)\bigr),\qquad n\in\N. \] Consequently, $v$ has at most one neighbor in each child cone of $t$. \end{enumerate} \end{lemma} \begin{proof} The first assertion follows from the range in \eqref{eq:phi} and the definition \eqref{eq:edges}. Nodes in distinct child cones are incomparable, which proves the second assertion. If an edge from $(t,b)$ has its other endpoint at greater height, then $(t,b)$ is the lower endpoint in \eqref{eq:edges}. This proves the displayed description of its upper neighbors. The words $b\res n$ have distinct lengths and therefore label distinct child cones, proving the last assertion. \end{proof} \section{The chromatic number} The function $(t,b)\mapsto\height(t)$ is a proper coloring by $\omega_1$, by Lemma~\ref{lem:incidence}. Thus $\chi(G)\leq\aleph_1$. To obtain equality, we show that every function $f:V\to\N$ assigns the same color to the endpoints of some edge. For a fixed $f:V\to\N$, put \[ P(t)=f[C(t)]\subseteq\N. \] Each $P(t)$ is nonempty, and $t\preceq u$ implies $P(u)\subseteq P(t)$. \begin{lemma}\label{lem:stabilization} There is a node $t_*\in T$ such that \begin{equation}\label{eq:stable} P(u)=P(t_*)\qquad\text{for every }u\succeq t_*. \end{equation} \end{lemma} \begin{proof} Starting with the root $t_0$, construct nodes $t_n$ recursively. At stage $n$, if there is an extension $u\succeq t_n$ with $n\notin P(u)$, choose one and set $t_{n+1}=u$. If there is no such extension, set $t_{n+1}=t_n$. The nodes form an increasing sequence. Their union \[ t_*=\bigcup_{n<\omega}t_n \] is a node of $T$, since its domain is the supremum of countably many countable ordinals and is therefore countable. Let $u\succeq t_*$. Monotonicity gives $P(u)\subseteq P(t_*)$. Conversely, suppose that $n\in P(t_*)$. Color $n$ was not removed at stage $n$, since removal would imply $n\notin P(t_{n+1})$ and hence $n\notin P(t_*)$. Therefore every extension of $t_n$ has color $n$ in its cone. As $u\succeq t_*\succeq t_n$, we have $n\in P(u)$. \end{proof} \begin{proposition}\label{prop:chromatic} The graph $G$ has chromatic number $\aleph_1$. \end{proposition} \begin{proof} Suppose that $f:V\to\N$ is a proper coloring, and take $t_*$ as in Lemma~\ref{lem:stabilization}. Choose a sequence $(k_n)_{n\in\N}$ whose range is $P(t_*)$. If this set is finite, repeat its elements. We construct $b\in A^{\N}$ recursively. Once $b\res n$ is known, \eqref{eq:stable} applied to $t_*\fcat\langle b\res n\rangle$ gives a vertex $w_n\in C(t_*,b\res n)$ with $f(w_n)=k_n$. Define \[ b(n)=\phi_{t_*,b\res n}^{-1}(w_n). \] The resulting vertex $v=(t_*,b)$ belongs to $C(t_*)$, so $f(v)\in P(t_*)$. Choose $m$ with $k_m=f(v)$. By construction, \[ \{v,w_m\}\in E(G) \quad\text{and}\quad f(w_m)=k_m=f(v), \] contradicting properness. Hence $G$ has no countable proper coloring. Together with the height coloring, this gives $\chi(G)=\aleph_1$. \end{proof} \section{Finite separators inside a cone} Fix $t\in T$ and a nonempty word $p\in L$ of length $k$. Define \begin{align} D(t,p) &=\{(t,b):p\sqsubseteq b\} \ \cup\!\bigcup_{\substack{s\in L\\p\sqsubseteq s}}C(t,s), \label{eq:region}\\ F(t,p) &=\left\{\phi_{t,p\res j}\bigl(p(j)\bigr):0\leq j