Converting connected graph to disconnected graph by removing minimum vertices
The minimum number of vertices that have to be removed in order to disconnect the graph is known at the connectivity of the graph. Wikipedia outlines an algorithm for finding the connectivity of a graph. More efficient algorithms might exist.

A related problem is the vertex separator problem, in which we want to disconnect two specific vertices by removing the minimal number of vertices.