Thin ends and topological spanning trees

Halin conjectured in 1964 that every connected graph has an end-faithful spanning tree. He proved this for countable graphs, but in the early 1990s Seymour and Thomas and, independently, Thomassen found uncountable counterexamples. Both are infinitely connected and hence one-ended, and their unique end has uncountable degree (i.e.\ contains uncountably many pairwise disjoint rays). Several authors have since asked how much of the conjecture survives. Diestel asked in 1992 whether a graph has an end-faithful spanning tree as soon as all its one-ended connected subgraphs have one; by a theorem of Polat, this would give end-faithful spanning trees in all connected graphs whose ends have countable degree. Diestel and Kühn introduced topological spanning trees, a topological variant of end-faithful spanning trees that exists in every one-ended connected graph, and asked in 2004 whether every connected graph has one. And Carmesin asked in 2019 whether every graph has a spanning tree that is end-faithful at least for its thin ends, the ends of finite degree. We answer all three questions in the negative. We show that the uncountably chromatic graph from an earlier note of ours on a problem of Erdős and Hajnal has only ends of countable degree, each dominated by only countably many vertices, yet it has neither an end-faithful nor a topological spanning tree. A refinement of this graph moreover has no spanning tree that contains a ray from every end of degree~1.

Authors

Publication Details

Journal
arXiv (Cornell University)
Published
2026-10-29
DOI
https://doi.org/10.48550/arxiv.2610.40458
Primary Topic
Advanced Graph Theory Research
Type
preprint
Controls
|||
ALL TIME
JAN
FEB
MAR
APR
MAY
JUN
JUL
AUG
SEP
OCT
preprint

Thin ends and topological spanning trees

Max F. Pitz, Nathan Bowler
arXiv (Cornell University)
Advanced Graph Theory Research
preprint

Thin ends and topological spanning trees

Max F. Pitz, Nathan Bowler
preprint en

Abstract

Halin conjectured in 1964 that every connected graph has an end-faithful spanning tree. He proved this for countable graphs, but in the early 1990s Seymour and Thomas and, independently, Thomassen found uncountable counterexamples. Both are infinitely connected and hence one-ended, and their unique end has uncountable degree (i.e.\ contains uncountably many pairwise disjoint rays). Several authors have since asked how much of the conjecture survives. Diestel asked in 1992 whether a graph has an end-faithful spanning tree as soon as all its one-ended connected subgraphs have one; by a theorem of Polat, this would give end-faithful spanning trees in all connected graphs whose ends have countable degree. Diestel and Kühn introduced topological spanning trees, a topological variant of end-faithful spanning trees that exists in every one-ended connected graph, and asked in 2004 whether every connected graph has one. And Carmesin asked in 2019 whether every graph has a spanning tree that is end-faithful at least for its thin ends, the ends of finite degree. We answer all three questions in the negative. We show that the uncountably chromatic graph from an earlier note of ours on a problem of Erdős and Hajnal has only ends of countable degree, each dominated by only countably many vertices, yet it has neither an end-faithful nor a topological spanning tree. A refinement of this graph moreover has no spanning tree that contains a ray from every end of degree~1.

arXiv (Cornell University)
Advanced Graph Theory Research
AI Navigator

Ask Laika to Summarize, Analyze, and Connect papers live on the map.

Summarize Papers & Methodologies

Extract key findings, datasets, and comparative methods across publications.

Benchmark Rankings & Visual Analytics

Rank top research institutions, authors, funders, topics, and journals by Field-Weighted Citation Impact (FWCI) and paper volume with instant charts.

Connect Distant Disciplines

Bridge topological clusters on the map to find hidden collaborative intersections.

Laika access coming soon