2
$\begingroup$

How to find the minimum number of vertices that need to be removed from a graph so it makes a disconnected graph?

$\endgroup$
2
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.