Isolating highly connected induced subgraphs

We prove that any graph G of minimum degree greater than 2k(2) - 1 has a (k + 1)-connected induced subgraph H such that the number of vertices of H that have neighbors outside of H is at most 2k(2) - 1. This generalizes a classical result of Mader, which states that a high minimum degree implies the existence of a highly connected subgraph. We give several variants of our result, and for each of these variants, we give asymptotics for the bounds. We also compute optimal values for the case when k = 2. Alon, Kleitman, Saks, Seymour, and Thomassen proved that in a graph of high chromatic number, there exists an induced subgraph of high connectivity and high chromatic number. We give a new proof of this theorem with a better bound.