---

Claim. There is a graph $X$ with chromatic number $\aleph_1$ such that no uncountable set of its vertices induces an infinitely connected subgraph, where a graph is infinitely connected when any two of its vertices are joined by infinitely many pairwise disjoint paths. Since a graph of chromatic number $\aleph_1$ is uncountable, $X$ has no infinitely connected subgraph of chromatic number $\aleph_1$, and the question of Problem 1067 has a negative answer in ZFC alone. This is Theorem 3.5 of arXiv:1409.2922v1, posted 2014-09-09, published as Dániel T. Soukup, Trees, ladders and graphs, J. Combin. Theory Ser. B 115 (2015), 96--116; Theorem 4.3 of the same version strengthens the construction so that any two incomparable vertices of the underlying tree are separated by a finite set, so every uncountable vertex set contains two vertices joined by only finitely many disjoint paths. The source card records the statements.

Argument, in outline. For a stationary costationary set $S\subseteq\omega_1$, the tree $T=T(S)$ of the paper's Section 2 has no uncountable chains and no branching at limit levels, and $G(T)$ is its comparability graph. A ladder system on $T$ assigns to each vertex $t$ a set $C_t$ of predecessors of $t$ that is either finite or a cofinal sequence of order type $\omega$ (Definition 3.1), and defines the subgraph $X_{\underline{C}}$ of $G(T)$ whose edges join each $t$ to the members of $C_t$. The system is transitive when $C_t\cap s^\downarrow\subseteq C_s$ for every $s\in C_t$ (Definition 3.2), so that each $C_t$ spans a complete subgraph; a path in $X_{\underline{C}}$ then contains a path that is the union of two monotone paths (Lemma 3.3). The separation property comes from transitivity and the two tree properties (Lemma 3.4): two incomparable vertices $s,t$ of an uncountable set $A$ have a greatest common initial part $r$, because $T$ does not branch at limits, and a suitable $s'\in A$ with $r<s'\leq s$ is separated from $t$ within $A$ by $\{r\}\cup(r^\downarrow\cap C_{s'})$, a finite set because $C_{s'}$ has order type at most $\omega$ and only its part below $r$ enters. The uncountable chromatic number is not a consequence of the tree alone: the proof of Theorem 3.5 builds a transitive ladder system by induction over the accumulation points of $S$, choosing at each level $\delta\in S$ the ladders of continuum many vertices against an enumeration of the countable colored subsets of the levels below, and an elementary-submodel argument (Claim 3.5.1) then shows that every coloring of $X_{\underline{C}}$ by $\omega$ colors gives an edge with both ends of one color. The proof was not reconstructed here.

Context. Erdős and Hajnal asked in 1966, for graphs with $\aleph_1$ vertices and chromatic number $\aleph_1$, whether an infinitely connected subgraph of chromatic number $\aleph_1$ must exist (source card), and in 1985 (Discrete Math. 53 (1985), 281--285) asked the question as the problem states it; Komjáth showed the 1966 version independent of ZFC. Komjáth, A note on chromatic number and connectivity of infinite graphs, Israel J. Math. 196 (2013), 499--506, showed earlier that a negative answer to the 1985 question is consistent with ZFC, by forcing a graph of size and chromatic number $\aleph_1$ with no uncountable infinitely connected subgraph (correcting the forcing of Komjáth's 1988 paper). Soukup's theorem needs neither forcing nor extra axioms. A later, shorter construction is Bowler and Pitz's example, which is independent of this one.

Acceptance. The result appeared in a refereed journal, the Journal of Combinatorial Theory, Series B, in 2015, the refereed evidence; the text cited here is the arXiv preprint (v1), not compared with the published version. The site's curator, Thomas Bloom, marks the problem DISPROVED (LEAN) and records in the commentary that Soukup constructed a counterexample using no extra set-theoretic assumptions: that curator credit is the reviewed evidence. The Lean development recorded on the Bowler and Pitz page formalizes their example, not this construction; neither the site's thread nor the formal-conjectures file at its revision of 2026-10-07 names a formalization of this construction, and this project has built or audited none.