# 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?

-
It should work (I assume all edges have the same capacity). – A.Schulz Dec 17 '12 at 9:26
Check this question on CSTheory – adrianN Sep 4 '14 at 12:15

2. 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}$.
3. Try to find a minimum cut $M$. The edges of $M$ refer to the vertices that we need to remove.
It's not clear to me why this would be guaranteed towork. What if the minimum cut of the modified graph includes some edges that are not between some $v_\text{in}$ and $v_\text{out}$, but are a directed edge from step 1 of the solution? Why do you think that each min-vertex-cut of the original graph will be in one-to-one correspondence with a min-edge-cut of the modified graph? I think a proof is needed. – D.W. Sep 5 '14 at 6:02