We prove that a connected infinite graph has a normal spanning tree (the infinite analogue of a depth-first search tree) if and only if it has no minor obtained canonically from either an aleph0-aleph1-regular bipartite graph or an order-theoretic Aronszajn tree. This disproves Halin's conjecture that only the first of these obstructions was needed to characterize the graphs with normal spanning tree s. As a corollary we deduce Halin's further conjecture that a connected graph has a normal spanning tree if and only if all its minors have countable colouring number.
The precise classification of the aleph0-aleph1-regular bipartite graphs remains an open problem. One such class turns out to contain obvious infinite minor-antichains, so as an unexpected corollary we reobtain Thomas's result that the infinite graphs are not well-quasi-ordered as minors.
Download (PDF)