Normal spanning trees, Aronszajn trees and excluded minors

It is proved that a connected infinite graph has a normal spanning tree (th e infinite analogue of a depth-first search tree) if and only if it has no minor obtained canonically from either an (N-0, N-1)-regular bipartite grap h or an order-theoretic Aronszajn tree. This disproves Halin's conjecture t hat only the first of these obstructions was needed to characterize the gra phs with normal spanning trees. As a corollary Halin's further conjecture i s deduced, that a connected graph has a normal spanning tree if and only if all its miners have countable colouring number. The precise classification of the (N-0, N-1)-regular bipartite graphs remai ns an open problem. One such class turns out to contain obvious infinite mi nor-antichains, so as an unexpected corollary Thomas's result that the infi nite graphs are not well-quasi-ordered as miners is reobtained.