Remove minimum number of vertices to disconnect the graph
(This answer was originally given as part of the question, with the goal of it being verified.)

My intuition tells me that we can use max-flow, min-cut algorithm to solve this problem:


Replace each of the undirected edges with a pair of directed edges.
Replace each vertex $v$ with two vertices $v_\text{in}$ and $v_\text{out}$ connected by an edge. all the incoming edges of $v$ will be connected with $v_\text{in}$, all the outgoing edges of $v$ will be connected with $v_\text{out}$.
Try to find a minimum cut $M$. The edges of $M$ refer to the vertices that we need to remove.