####

#### Normal spanning trees, Aronszajn trees and excluded
minors

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)