Thin ends and topological spanning trees
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.
Related
- Spectral radius and edge-disjoint spanning trees of graphs with edge connectivity
- A quadratic ancestor inequality for spanning trees
- Spanning k-trees and the colorful Carathéodory theorem
- On Hypergraph Colorings and Completely Independent Spanning Trees in Chordal Graphs
- Constructing two completely independent spanning trees in dual-cubes
BibTeX
@misc{bowler2026thin,
title = {{Thin ends and topological spanning trees}},
author = {Nathan Bowler and Max Pitz},
howpublished = {arXiv},
year = {2026},
month = oct,
doi = {10.48550/arxiv.2610.40458},
eprint = {2610.40458},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2610.40458},
note = {CC BY-NC-ND 4.0},
}
RIS
TY - UNPB
TI - Thin ends and topological spanning trees
AU - Nathan Bowler
AU - Max Pitz
PY - 2026
DA - 2026/10/29
PB - arXiv
DO - 10.48550/arxiv.2610.40458
UR - https://arxiv.org/abs/2610.40458
AB - 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.
ER -