Ka,k Minors in Graphs of Bounded Tree-Width

AbstractIt is shown that for any positive integers k and w there exists a constant N=N(k,w) such that every 7-connected graph of tree-width less than w and of order at least N contains K3,k as a minor. Similar result is proved for Ka,k minors where a is an arbitrary fixed integer and the required connectivity depends only on a. These are the first results of this type where fixed connectivity forces arbitrarily large (nontrivial) minors