Making the components of a graph \(k\)-connected (Q868399)

For \(k \geq 2\) it is shown that if \(G\) is a graph of order \(n\) with \(\delta(G) \geq \sqrt{2(k - 1)n}\), then there is a set \(X\) with \(| X| \leq \delta - (k - 3)/2 - \sqrt{(\delta + (k+1)/2)^2 - 2n(k - 1)}\) such that each component of \(G - X\) is \(k\)-connected. More specifically a \(k\)-cutting procedure of deleting components with at most \(k\) vertices and cutsets with less that \(k\) vertices in components that are not \(k\)-connected is described that results in a graph that has each component \(k\)-connected. The previously stated result is a corollary of this procedure, and the bound on the deleted set in the \(k\)-cutting procedure is essentially sharp and cannot be improved. Still remaining is the open question of a sharp condition on the minimum degree that is needed to imply the existence of a deletion set of a given size will result in a graph with each component \(k\)-connected.