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.