Remove minimum number of vertices to disconnect the graph Consider an undirected graph with a source and a sink vertex. We would like to remove minimum number of vertices in that graph to disconnect any path between source and sink.

Can we do this using say a max-flow, min-cut algorithm?
(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.