How to find the minimum number of vertices that need to be removed from a graph so it makes a disconnected graph?
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.