Making the components of a graph k-connected

For every integer k ≥ 2 and graph G, consider the following natural procedure: if G has a component G′ that is not k-connected, remove G′ if | G′ | ≤ k, otherwise remove a cutset U ⊂ V (G′) with | U | \u3c k; do the same with the remaining graph until only k-connected components are left or all vertices are removed. We are interested when this procedure stops after removing o (| G |) vertices. Surprisingly, for every graph G of order n with minimum degree δ (G) ≥ sqrt(2 (k - 1) n), the procedure always stops after removing at most 2 n (k - 1) / δ vertices. We give examples showing that our bounds are essentially best possible. © 2006 Elsevier B.V. All rights reserved