Many disjoint dense subgraphs versus large kk-connected subgraphs in large graphs with given edge density

It is proved that for all positive integers d,k,s,td,k,s,t with t≥k+1t≥k+1 there is a positive integer M=M(d,k,s,t)M=M(d,k,s,t) such that every graph with edge density at least d+kd+k and at least MM vertices contains a kk-connected subgraph on at least tt vertices, or ss pairwise disjoint subgraphs with edge density at least dd. By a classical result of Mader [W. Mader, Existenz nn-fach zusammenhängender Teilgraphen in Graphen genügend großer Kantendichte, Abh. Math. Sem Univ. Hamburg, 37 (1972) 86–97] this implies that every graph with edge density at least 3k3k and sufficiently many vertices contains a kk-connected subgraph with at least rr vertices, or rr pairwise disjoint kk-connected subgraphs. Another classical result of Mader [W. Mader, Homomorphiesätze für Graphen, Math. Ann. 178 (1968) 154–168] states that for every nn there is an l(n)l(n) such that every graph with edge density at least l(n)l(n) contains a minor isomorphic to KnKn. Recently, it was proved in [T. Böhme, K. Kawarabayashi, J. Maharry, B. Mohar, Linear connectivity forces dense minors, J. Combin. Theory Ser. B (submitted for publication)] that every (312a+1)-connected graph with sufficiently many vertices either has a topological minor isomorphic to Ka,pqKa,pq, or it has a minor isomorphic to the disjoint union of pp copies of Ka,qKa,q. Combining these results with the result of the present note shows that every graph with edge density at least l(a)+(312a+1) and sufficiently many vertices has a topological minor isomorphic to Ka,paKa,pa, or a minor isomorphic to the disjoint union of pp copies of KaKa. This implies an affirmative answer to a question of Fon-der-Flaass.