Abstract
We show that every connected graph can be approximated by a normal tree, up to some arbitrarily small error phrased in terms of neighbourhoods around its ends. The existence of such approximate normal trees has consequences of both combinatorial and topological nature.
On the combinatorial side, we show that a graph has a normal spanning tree as soon as it has normal spanning trees locally at each end; i.e., the only obstruction for a graph to having a normal spanning tree is an end for which none of its neighbourhoods has a normal spanning tree.
On the topological side, we show that the end space Ω(G), as well as the spaces |G| = G ∪ Ω(G) naturally associated with a graph G, are always paracompact. This gives unified and short proofs for a number of results by Diestel, Sprüssel and Polat, and answers an open question about metrizability of end spaces by Polat.
On the combinatorial side, we show that a graph has a normal spanning tree as soon as it has normal spanning trees locally at each end; i.e., the only obstruction for a graph to having a normal spanning tree is an end for which none of its neighbourhoods has a normal spanning tree.
On the topological side, we show that the end space Ω(G), as well as the spaces |G| = G ∪ Ω(G) naturally associated with a graph G, are always paracompact. This gives unified and short proofs for a number of results by Diestel, Sprüssel and Polat, and answers an open question about metrizability of end spaces by Polat.
Original language | English |
---|---|
Pages (from-to) | 173-183 |
Number of pages | 11 |
Journal | Journal of Combinatorial Theory, Series B |
Volume | 148 |
Early online date | 15 Jan 2021 |
DOIs | |
Publication status | Published - May 2021 |
Keywords
- Infinite graph
- End
- End space
- Paracompact
- Normal spanning tree