[Math] Remove minimum number of nodes to make graph disconnected

Question

Find the minimum number of nodes that need to be removed to make graph disconnected( there exists no path from some node x to all other nodes). Number of nodes can be 10⁵

Answer 1

You are searching for the minimum $k$ such that your graph $G = (V, E)$ is $k$-vertex-connected.

To solve this problem consider Menger's theorem:

Let $G$ be a finite undirected graph and $x$ and $y$ two nonadjacent vertices. Then the size of the minimum vertex cut for $x$ and $y$ (the minimum number of vertices, distinct from $x$ and $y$, whose removal disconnects $x$ and $y$) is equal to the maximum number of pairwise internally vertex-disjoint paths from $x$ to $y$.

(from Wikipedia)

You can find such paths using a reduction of the vertex-version of Menger's theorem to the edge-version of Menger's theorem, which may be solved in a variety of ways, e.g. by solving a max-flow problem.

$k$ is the minimum over the cardinality of a minimum vertex cut for $(u, v)$ for every pair $(u, v)$ of non-adjacent nodes in $G$. $$ k = \min \left\{ \text{cardinality of minimum $u$-$v$-cut} \mid (u, v) \in V \times V, u~\text{and}~v~\text{are non-adjacent} \right\} $$