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

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