Premium
Normal Spanning Trees, Aronszajn Trees and Excluded Minors
Author(s) -
Diestel Reinhard,
Leader Imre
Publication year - 2001
Publication title -
journal of the london mathematical society
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 1.441
H-Index - 62
eISSN - 1469-7750
pISSN - 0024-6107
DOI - 10.1112/s0024610700001708
Subject(s) - combinatorics , mathematics , bipartite graph , corollary , spanning tree , conjecture , countable set , discrete mathematics , tree (set theory) , graph
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.