# Graph Connectivity

Given a graph $G = (V, E)$, I need to determine:

1. $k$, the graph connectivity.
2. Which are those $k$ vertices to remove to make $G$ disconnected.

Questions

• Which is the complexity of such problem?
• Which are the fastest algorithms known?
• What about if, additionally, I require that the resulting connected components have almost the same number of edges?

This question is an improvement of this question.

Both can be done efficiently. You can compute the connectivity of a graph by testing the connectivity of every pair using max-flow/min-cut and taking the smallest of the values gives you $k$ (see this on Menger's theorem) -- this gives you (1). Using the procedure above, you can test each vertex, one at a time, to see if its removal will decrease the connectivity. Once you find such a vertex, remove it and proceed -- this gives you (2).