Normal Spanning Trees, Aronszajn Trees and Excluded Minors

Abstract

It is proved 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 (ℵ0, ℵ1)-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 trees. As a corollary Halin's further conjecture is deduced, 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 (ℵ0, ℵ1)-regular bipartite graphs remains an open problem. One such class turns out to contain obvious infinite minor-antichains, so as an unexpected corollary Thomas's result that the infinite graphs are not well-quasi-ordered as minors is reobtained.