Erdoes #1068 - working report - Erdős Problem a Day

Erdős problem #1068 — live audit, an explicit \(K_{\aleph_0}\), and the exact remaining wall

Access/search date: 2026-07-27 UTC.

Claim labels used throughout:

(a) elementary-rigorous;
(b) rigorous modulo the stated named theorem or primary source;
(c) plausible/structural-unverified (including literature-search completeness);
(d) computational-only.

Result in one paragraph

The problem is still open; this report does not claim a solution. The verified

progress is that the Bowler--Pitz graph cited on the live page is not a

counterexample even at the countable level: it contains the explicit complete

graph

\[ p_n=(2,4,\ldots,2n)\qquad(n<\omega). \]

More generally, any graph carried by a well-founded order in which every lower

neighbourhood is a clique is either countably chromatic or contains

\(K_{\aleph_0}\). This covers the Bowler--Pitz construction and the transitive

ladder-system machinery used by Soukup. (a) The report also gives an exact

closed form and checked table for natural finite truncations of the

Bowler--Pitz graph. Finally, two elementary examples isolate why the usual

ambient-block/minor and “\(n\)-connected for every finite \(n\)” approaches do

not compactify to the desired subgraph. (a)

0. Mandatory live-page gate

I fetched the following through the Bright Data cloud browser, not through

datacenter curl:

which redirects to /forum/thread/1068.

The rendered live page displayed:

OPEN;
0 claimed proofs for this problem;
Interested in collaborating: None;
Currently working on this problem: None;
This problem looks difficult: None;
This problem looks tractable: None;
The results on this problem could be formalisable: None;
I am working on formalising the results on this problem: None;
Formalised statement? Yes;
two comments;
last edited 23 January 2026.

The only “likes” shown were ebarschkis, Dogmachine. Thus no stop/collision

condition fired. (b, source-verified)

Verbatim current statement

> Does every graph with chromatic number \(\aleph_1\) contain a countable subgraph which is infinitely vertex-connected?

The page defines “infinitely (vertex) connected” to mean that every two

vertices are joined by infinitely many pairwise vertex-disjoint paths (with the

usual convention that the common endpoints are allowed). **(b,

source-verified)**

All known-results text displayed on the live page

The page says this is described by Bowler and Pitz as a version of the

Erdős--Hajnal problem (#1067), but apparently is not in the cited 1966

Erdős--Hajnal paper. It records that Soukup constructed an uncountably

chromatic graph in which every uncountable vertex set has two vertices with

only finitely many independent paths between them, and that Bowler and Pitz

gave a simpler construction. It links #1067. **(b, source-verified as a report

of what the page says; I do not promote its “does not seem to appear” remark to

an independently proved absence claim.)**

Both displayed comments

The forum explicitly warns that comments are not verified. I read both:

1. ebarschkis, 18 January 2026, said the edge-connectivity interpretation is

solved by Thomassen, while the vertex-connectivity interpretation remains

open, and also pointed out that the desired subgraph need not be

uncountable.

2. Thomas Bloom replied the same day that vertex-connectivity was intended and

that he had edited the statement to say so.

Neither comment contains a proof claim or a current-worker marker. **(b,

faithful source audit, not an endorsement of an unverified comment)**

1. Primary-source literature audit

Bowler--Pitz

Nathan Bowler and Max Pitz, [*A Note on Uncountably Chromatic

Graphs*](https://www.combinatorics.org/ojs/index.php/eljc/article/view/v32i1p23),

Electronic Journal of Combinatorics 32(1) (2025), #P1.23, DOI

10.37236/13359, exists and is the final

published version of arXiv:2402.05984. Its Theorem 1 gives the simpler ZFC

construction reported by the page. Remark 3 asks exactly whether every

uncountably chromatic graph has a countably infinite, infinitely connected

subgraph and says it remains open. (b)

The final paper defines, for every countable ordinal \(\alpha\),

\[ T^\alpha=\{t:\alpha\to\mathbb N:t\text{ injective and } |\mathbb N\setminus\operatorname{im}(t)|=\infty\}, \qquad T=\bigcup_{\alpha<\omega_1}T^\alpha, \]

ordered by extension. For a successor sequence \(s\), let \(s^*\) be its

immediate predecessor, and put

\[ A_t=\{s\le t:\ s\text{ has successor length and } \operatorname{last}(s)= \min(\operatorname{im}(t)\setminus\operatorname{im}(s^*))\}, \qquad A_t^*=\{s^*:s\in A_t\}. \]

Its graph \(\mathbf G\) has edges \(ut\) exactly when \(u\in A_t^*\).

(b, definition transcribed from the primary paper)

Soukup

Dániel T. Soukup, [*Trees, ladders and

graphs*](https://www.sciencedirect.com/science/article/pii/S0095895615000593),

Journal of Combinatorial Theory, Series B 115 (2015), 96--116, DOI

10.1016/j.jctb.2015.05.004,

exists and proves the ZFC result stated on the page. Its highly disconnected

construction (Theorem 4.3) is built from a transitive coherent ladder system.

Its Proposition 6.1 proves the stronger partition statement

\[ \chi(X_{\mathcal C})>\aleph_0,\quad \mathcal C\text{ transitive} \quad\Longrightarrow\quad X_{\mathcal C}\longrightarrow(K_{\omega+1})^1_\omega. \]

In particular, Soukup's page-cited construction already contains countably

infinite complete subgraphs. (b) This agrees with Soukup's thesis

discussion, which explicitly says his construction contains several such

cliques.

Finite vertex-connectivity and the edge version

Péter Komjáth, [*Connectivity and chromatic number of infinite

graphs](https://link.springer.com/article/10.1007/BF02782936), Israel

Journal of Mathematics* 56 (1986), 257--266, DOI

10.1007/BF02782936, has the primary

abstract:

every uncountably chromatic graph contains, for every finite \(n\), an

\(n\)-connected uncountably chromatic subgraph all of whose degrees are

infinite. (b)

Carsten Thomassen, [*Infinitely connected subgraphs in graphs of uncountable

chromatic

number*](https://orbit.dtu.dk/en/publications/infinitely-connected-subgraphs-in-graphs-of-uncountable-chromatic/),

Combinatorica 37 (2017), 785--793, DOI

10.1007/s00493-016-3436-4,

proves that every uncountably chromatic graph has an uncountably chromatic

subgraph of infinite edge-connectivity. The accepted manuscript was also

read; its proof is by generalized finite-edge-cut deletions and a reconstruction

by finite-edge-cut additions. It does not prove vertex-connectivity. (b)

Current-search result

Exact-phrase searches for the countable version, searches using

“\(\aleph_0\)-block”, and forward-citation queries for the Bowler--Pitz DOI

found the sources above but no later primary paper claiming a proof or

counterexample. OpenAlex and Semantic Scholar each returned zero forward

citations for that DOI on the access date. Database coverage can be incomplete,

so this is an honest search miss, not a theorem that no later work exists.

(c)

I did not locate a reliable scan of the 1999 Va99 booklet item 7.90 during

the targeted search. I therefore use the mandated live-page statement, not a

reconstruction of the booklet wording. The primary Bowler--Pitz paper is the

most recent located paper to formulate exactly this countable question. **(c

for search completeness; no mathematical claim is based on the missing scan)**

2. A positive theorem for the structure used by both cited constructions

Lemma (well-founded lower-clique lemma)

Let \(G=(V,E)\) admit a strict well-founded partial order \(\prec\) such that:

1. the endpoints of every edge are comparable; and

2. for every \(v\), its lower neighbourhood

\[ L(v)=\{u\prec v:uv\in E\} \]

induces a clique.

Then either \(\chi(G)\le\aleph_0\), or \(G\) contains

\(K_{\aleph_0}\). (a)

Proof

Assume \(G\) has no \(K_{\aleph_0}\). Each \(L(v)\) is a clique, so it must be

finite: any infinite set has a countably infinite subset in ZFC. By

well-founded recursion, assign

\[ c(v)=\min\bigl(\mathbb N\setminus c[L(v)]\bigr). \]

This is defined because \(L(v)\) is finite. If \(uv\in E\), say \(u\prec v\),

then \(u\in L(v)\), so \(c(u)\ne c(v)\). Thus \(c\) is a proper countable

colouring. Taking the contrapositive proves the lemma. \(\square\)

This statement is not claimed as a new theorem; its value here is that it

pinpoints a simple hereditary structural reason the standard transitive

ladder constructions cannot refute #1068.

Application to the Bowler--Pitz graph

Every edge of \(\mathbf G\) joins two comparable tree nodes. Moreover,

\[ L(t)=A_t^* \]

is a clique. To check the latter directly, take distinct \(u,v\in A_t^*\)

with \(u \[ \min(\operatorname{im}(t)\setminus\operatorname{im}(u)). \]

That successor already lies below \(v\); restricting the set over which the

minimum is taken from the tail of \(t\) to the segment ending at \(v\)

therefore leaves the same minimum. Hence \(u\in A_v^*\), so \(uv\) is an

edge. (a)

The extension order is well-founded, so the lemma applies: every

uncountably chromatic graph of this ordered-lower-clique form contains

\(K_{\aleph_0}\). (a)

Closed-form clique in \(\mathbf G\)

There is an even more direct certificate. For \(n<\omega\), define

\[ p_n=(2,4,\ldots,2n), \]

with \(p_0\) the empty sequence. Every \(p_n\) is a vertex of \(T\), since it

is a finite injective sequence and hence has co-infinite complement in

\(\mathbb N\).

If \(m \[ 2(m+1)=\min\{2(m+1),2(m+2),\ldots,2n\}. \]

Thus \(p_m\in A_{p_n}^*\), so \(p_mp_n\in E(\mathbf G)\). Consequently

\[ \mathbf G[\{p_n:n<\omega\}]\cong K_{\aleph_0}. \tag{1} \]

(a)

For any two \(p_i,p_j\), the length-two paths

\[ p_i\,p_k\,p_j\qquad(k\notin\{i,j\}) \]

have pairwise distinct internal vertices. Hence (1) is infinitely

vertex-connected in precisely the live page's sense. (a)

This does not solve the universal problem. It does rigorously eliminate the

newest/simple page-cited construction as a possible counterexample and, via

the lemma, eliminates the whole well-founded lower-clique template.

3. Exact finite truncations of the Bowler--Pitz graph

For \(q\ge1\), let

\[ T_q=\{t:t\text{ is an injective word over }[q]\} \]

including the empty word, with the Bowler--Pitz adjacency inherited from

\(\mathbf G\). Every word here is a genuine vertex of the infinite graph.

For a word \(t=(t_0,\ldots,t_{k-1})\), the set \(A_t^*\) consists exactly of

the prefixes just before the right-to-left minima:

\[ t{\upharpoonright}i\in A_t^* \quad\Longleftrightarrow\quad t_i=\min\{t_i,t_{i+1},\ldots,t_{k-1}\}. \tag{2} \]

(a)

Write \((q)_k=q!/(q-k)!\) and \(H_k=\sum_{i=1}^k1/i\). Then

\[ \begin{aligned} |V(T_q)|&=\sum_{k=0}^q(q)_k,\\ |E(T_q)|&=\sum_{k=1}^q(q)_k H_k,\\ \omega(T_q)&=\chi(T_q)=q+1. \tag{3} \end{aligned} \]

(a)

For the edge count, every edge has a unique upper endpoint \(t\), and (2)

counts its lower neighbours. A uniformly ordered \(k\)-set has expected

\(H_k\) right-to-left minima; equivalently, the element at reverse position

\(i\) is a new minimum in exactly a \(1/i\) fraction of the orders. Summing

over all \((q)_k\) injective words gives the second formula. For the chromatic

number, word length gives \(q+1\) colours, while

\[ (),\ (1),\ (1,2),\ldots,(1,2,\ldots,q) \]

is a clique of size \(q+1\). (a)

The standalone verifier recomputed:

|---:|---:|---:|---:|

| 1 | 2 | 1 | 2 |

| 2 | 5 | 5 | 3 |

| 3 | 16 | 23 | 4 |

| 4 | 65 | 116 | 5 |

| 5 | 326 | 669 | 6 |

| 6 | 1,957 | 4,429 | 7 |

| 7 | 13,700 | 33,375 | 8 |

The table is (d); formula (3) and its certificates are (a). The code

computes \(A_t^*\) twice, once literally from the set-difference definition

and once from suffix records, and requires equality on every one of the

13,700 nodes at \(q=7\).

4. Why two tempting compactness reductions fail

4.1 Ambient finite inseparability is not enough

Let \(S(K_{\aleph_0})\) be obtained from a countably infinite complete graph

on branch vertices \(b_0,b_1,\ldots\) by subdividing every edge once; call

the subdivision vertex on \(b_ib_j\) by \(s_{ij}\).

For fixed \(i\ne j\), there are infinitely many internally disjoint

\(b_i\)-\(b_j\) paths in the ambient graph:

\[ b_i s_{ij} b_j,\qquad b_i s_{ik} b_k s_{kj} b_j\quad(k\notin\{i,j\}). \]

Thus the branch vertices are pairwise inseparable by finite ambient vertex

sets. (a)

Nevertheless \(S(K_{\aleph_0})\) contains no infinitely vertex-connected

subgraph. Every vertex of an infinitely vertex-connected graph has infinite

degree: the first internal step of pairwise internally disjoint paths must

use distinct neighbours (apart from the possible direct path). Every

subdivision vertex has ambient degree two. Every nontrivial connected

subgraph contains an edge and hence a subdivision vertex, while a subgraph

using only branch vertices has no edges. (a)

Therefore finding a countable \(\aleph_0\)-block, a \(K_{\aleph_0}\) minor, or

pairwise ambient finite inseparability does not suffice. Infinite

vertex-connectivity of a subgraph is not subdivision invariant. This is

the exact obstruction to a straightforward tangle/block/minor reduction.

4.2 Arbitrarily large finite connectivity is not coherent connectivity

There is also a sharp elementary warning against diagonalising only the

finite \(n\)-connected conclusions.

Let \(R=\mathbb N^{<\omega}\) be the countable rooted tree of finite natural

sequences, with parent/child adjacency. Every vertex of \(R\) has countably

infinite degree. For \(n\ge1\), form the lexicographic clique blow-up

\[ B_n=R[K_n]. \]

Thus every base-tree vertex is replaced by an \(n\)-clique, and adjacent

fibres are joined completely.

The graph \(B_n\) has the following exact properties:

1. Every vertex has countably infinite degree. (a)

2. \(B_n\) is \(n\)-connected: after deleting fewer than \(n\) vertices,

every fibre still has a representative, and representatives along the

unique base-tree path connect any two surviving vertices. (a)

3. Its vertex connectivity is exactly \(n\): deleting one whole non-root

fibre separates a descendant side from the parent side. (a)

4. \(\chi(B_n)=2n\): two adjacent fibres form \(K_{2n}\), while the two

parity classes of the bipartite base tree can use disjoint \(n\)-colour

palettes. (a)

5. It has no infinitely vertex-connected subgraph. An infinite connected

subgraph projects to an infinite connected subtree of \(R\). Choose a

length-two path in that projected subtree; deleting the finite middle

fibre separates vertices over its two ends. A finite subgraph plainly

cannot have infinitely many internally disjoint paths. (a)

Consequently

\[ B=\coprod_{n\ge1}B_n \]

is countably chromatic, has for every finite \(n\) an \(n\)-connected

subgraph all of whose degrees are infinite, but has no infinitely

vertex-connected subgraph. (a)

This does not contradict Komjáth: his \(n\)-connected subgraphs are also

uncountably chromatic. It proves that connectivity plus infinite minimum

degree cannot itself be diagonalised; any successful argument must use the

uncountable-chromatic reservoir to make the finite linkages coherent on one

countable vertex set.

5. A clean decomposition reduction

The following elementary localisation makes one possible missing lemma

precise.

Tree-decomposition colouring lemma

If a graph \(G\) has a tree-decomposition \((B_t:t\in T)\) in which every

bag-induced graph \(G[B_t]\) is countably chromatic, then \(G\) is countably

chromatic. (a)

Proof

Root \(T\). The bags containing a vertex \(v\) form a connected subtree, so

they have a unique node \(r(v)\) nearest the root. Put

\[ X_t=\{v:r(v)=t\}\subseteq B_t \]

and choose a countable proper colouring \(c_t\) of \(G[X_t]\). Colour

\[ v\longmapsto \bigl(\operatorname{depth}(r(v)),c_{r(v)}(v)\bigr). \]

If adjacent \(u,v\) have introduction nodes at the same depth, both

introduction nodes lie on the root-to-bag path for a bag containing the

edge, so they are the same node; then \(c_t\) separates them. Different

depths are separated by the first coordinate. Since

\(\mathbb N\times\mathbb N\) is countable, this is a countable proper

colouring. \(\square\)

Hence a sufficient structural theorem for a positive answer would be:

> Every graph with no countable infinitely vertex-connected subgraph admits

> a tree-decomposition whose bags induce countably chromatic graphs.

No such theorem was located, and it cannot be replaced merely by a

decomposition displaying ambient \(\aleph_0\)-blocks, because the subdivided

complete-graph example above already separates ambient inseparability from

subgraph connectivity. **(c for existence of the missing structural theorem;

the implication from it is (a))**

Equivalently on the constructive side, one needs a rooted/coherent

strengthening of the Komjáth conclusion: increasing finite sets

\(X_1\subset X_2\subset\cdots\), with \(\left|\bigcup_mX_m\right|=\aleph_0\),

such that, for every \(m\), every pair in \(X_m\) has \(m\) internally

disjoint paths already inside \(G[X_{m+1}]\). Then

\(G[\bigcup_mX_m]\) is infinitely connected: any finite separator is smaller

than some certified linkage. (a) Komjáth's theorem supplies

highly connected uncountably chromatic subgraphs separately for each \(m\),

but does not keep earlier roots inside later subgraphs. The blow-up family

shows why that coherence is a real extra step.

6. Reverification code and runs

The standalone, dependency-free verifier is

erdos1068_wave6u_verify.py. It contains:

two independent implementations of \(A_t^*\);
exhaustive construction of every \(T_q\) for \(q\le7\);
direct clique and length-colouring certificates for (3);
a check of 40 vertices \(p_n\), all 780 pairs, and 39 internally disjoint

paths per pair in that finite restriction;

exhaustive enumeration of all \(2^{\binom n2}\) graphs for \(n\le6\),

retaining those whose earlier-neighbour sets are cliques and independently

checking that greedy colouring equals brute-force clique number;

finite checks of the subdivided-complete-graph path families;
exhaustive vertex-cut checks for finite path analogues of \(R[K_n]\) for

\(n\le4\).

Command run:

python runs/erdos1068_wave6u_verify.py

Output:

Bowler--Pitz finite truncations
q  vertices  edges  omega=chi
1         2      1          2
2         5      5          3
3        16     23          4
4        65    116          5
5       326    669          6
6      1957   4429          7
7     13700  33375          8

Explicit p_n=(2,4,...,2n) clique restriction
{'vertices_checked': 40, 'pairs_checked': 780,
 'internally_disjoint_paths_per_pair': 39}

Exhaustive ordered lower-neighbourhood-clique graphs
{'n': 1, 'valid_ordered_graphs': 1, 'by_clique_number': {1: 1}}
{'n': 2, 'valid_ordered_graphs': 2, 'by_clique_number': {1: 1, 2: 1}}
{'n': 3, 'valid_ordered_graphs': 7,
 'by_clique_number': {1: 1, 2: 5, 3: 1}}
{'n': 4, 'valid_ordered_graphs': 39,
 'by_clique_number': {1: 1, 2: 23, 3: 14, 4: 1}}
{'n': 5, 'valid_ordered_graphs': 324,
 'by_clique_number': {1: 1, 2: 119, 3: 171, 4: 32, 5: 1}}
{'n': 6, 'valid_ordered_graphs': 3839,
 'by_clique_number': {1: 1, 2: 719, 3: 2212, 4: 839, 5: 67, 6: 1}}

Once-subdivided complete graphs (last row)
{'branch_vertices': 10, 'total_vertices': 55,
 'paths_per_branch_pair': 9}

Finite path clique-blowups
{'fibre_size': 1, 'vertices': 5, 'vertex_connectivity': 1,
 'clique_and_chromatic_number': 2}
{'fibre_size': 2, 'vertices': 10, 'vertex_connectivity': 2,
 'clique_and_chromatic_number': 4}
{'fibre_size': 3, 'vertices': 15, 'vertex_connectivity': 3,
 'clique_and_chromatic_number': 6}
{'fibre_size': 4, 'vertices': 20, 'vertex_connectivity': 4,
 'clique_and_chromatic_number': 8}

ALL CHECKS PASSED

The run took 3.4 seconds on this VM. A second run with

PYTHONHASHSEED=123 also ended ALL CHECKS PASSED. python -m py_compile

passed. The verifier SHA-256 is

0279f7ca5180d7967d6b18ed24ab8c5aa6528d1c588d6b5f049943ea42aeb939.

(d)

7. Honest status

What is proved here is a positive result for the exact ordered/transitive

template behind both ZFC constructions cited on the page, plus an explicit

closed-form \(K_{\aleph_0}\) inside the newest one. This is genuine evidence

that those negative constructions stop exactly at “uncountable,” but it is

not a uniform theorem for arbitrary \(\aleph_1\)-chromatic graphs.

The exact unresolved step is chromatic coherence across all finite vertex

connectivities: either construct one countable set carrying arbitrarily large

rooted linkages, or prove a separator decomposition with countably chromatic

bags. Ambient \(\aleph_0\)-blocks/minors are too weak (subdivision example),

and the separate finite-\(n\) conclusions are too weak (clique-blown-up tree

example). No computation on finite truncations can supply the missing

uncountable uniformity.

PARTIAL: The two page-cited ZFC constructions are verified to contain \(K_{\aleph_0}\); an ordered lower-clique theorem and exact truncation formulas are proved, while the general problem remains open at the chromatic-coherence step.

This is the AI working report, labelled by outcome — not an independently verified claim unless marked PROVED. ← ledger