Linear connectivity forces large complete bipartite minors

Let a be an integer. It is proved that for any s and k, there exists a constant N = N ( s , k , a ) such that every 31 2 ( a + 1 ) -connected graph with at least N vertices either contains a subdivision of K a , s k or a minor isomorphic to s disjoint copies of K a , k . In fact, we prove that connectivity 3 a + 2 and minimum degree at least 31 2 ( a + 1 ) − 3 are enough while the other conditions cannot be weakened. = 1 and k = a , this implies that every 31 2 ( a + 1 ) -connected graph with at least N ( a ) vertices has a K a -minor. This is the first result where a linear lower bound on the connectivity in terms of the parameter a forces a K a -minor. This resolves a conjecture proposed by Mader [W. Mader, Existenz n-fach zusammenhängender Teilgraphen in Graphen genügend grosser Kantendichte, Abh. Math. Sem. Univ. Hamburg 37 (1972) 86–97] and Thomason [A. Thomason, An extremal function for contractions of graphs, Math. Proc. Cambridge Philos. Soc. 95 (1984) 261–265; A. Thomason, The extremal function for complete minors, J. Combin. Theory Ser. B 81 (2001) 318–338]. Our result also generalizes a recent result of Böhme and Kostochka [T. Böhme, A. Kostochka, Disjoint K r -minors in large graphs with given average degree, European J. Combin. 26 (2005) 289–292], resolves a conjecture of Fon-Der-Flaass [D. Fon-Der-Flaass, private communication], and has several other consequences.