Removing minimum no of edges to disconnect two vertices in a graph

Question

Here I am trying to disconnect two vertices in a graph with minimum edge removal possible.

In this graph between two vertices A and Z you can find the answer in many ways. In optimal way you can remove just one edge from A to B.

If there is any specific algorithm for this?

I found some suggestions to solve this by using maximum flow min cut problem but I am not getting general idea to convert this problem into max flow min cut theorem. Also in the process I might end up removing an edge between F and G which is useless.

Answer 1

This can be solved using Max Flow - Min Cut problem.

You can model your graph into network flow as follows:
1. Consider A to be the source vertex, Z to be the sink vertex.
2. Set the capacity of each edge to be 1 unit.

Now, solve the Max Flow - Min Cut problem in above network. With it you will be able to find number of edge-disjoint paths from A to Z. For every such path, remove the first edge (edge originating from source A).

Proof:
Observe that after removing above edges, you won't be able to reach A to Z. If you had a path, then Max flow algorithm would have included this path in set of edge-disjoint-paths.
Also, by construction of network, you can't remove lesser number of edges to disconnect A from Z