The edge-connectivity of an undirected graph is the minimum number k of edges that must be removed to disconnect the graph. i.e., 1 for a tree, 2 for a cycle. Give an algorithm for determining the edge connectivity of an undirected graph G = (V,E) which runs a max flow algorithm on |V | − 1 different flow networks, each with |V | nodes and |E| edges. What is its running time? 

can you help me to give the algorithm and running time with explanation?

 

Here Is Answer :

In this we know that for any two vertices, let's just say, u and v, in graph G we can define a flow network G_uv, consisting of the directed version of G with s =u, t=v and all edge capacities set to 1. (The flow network G_uv has V vertices and 2|E| edges, so that it has O(V) vertices and O(E) edges, as required. We want all capacities to be 1 so that the number of edges of G crossing a cut equals the capacity of the cut in G_uv).

So the algorithm:

Let f_uv denote a maximum flow in G_uv. We claim for any u ∈ V the edge connectivity k=min_v∈V-{u}{|f_uv|}

Assuming that it holds we can find k as follows:

Edge connectivity(G):

K=infinite

select any vertex u∈ G.V

for each vertex v ∈ G.V - {u}

Set up the flow network G_uv as described

Find the maximum flow f_uv on G_uv

k=min(k,|f_uv|)

Return k