# Edge-connectivity of a weighted undirected graph

My question consists of two parts.

1. Let say the edge connectivity of a graph is K. I would like to change the edge connectivity value to L (> K). What is the best possible way to do so?

My guess: Obviously, we have to increase the edge weight of one of the critical edges (edges of the min-cut), but among the set of critical edges which edge should we choose?

1. After changing the weight of one of the critical edges, how could we find the new edge connectivity of the graph [assume we have already computed the edge connectivity of the previous graph]?
• 1. Please ask only one question per post. 2. "best possible way" - This is subjective, as it's not clear what you mean by "best". What's best may be a matter of opinion. Can you specify how you will evaluate answers? What are your requirements? What approaches have you considered, and why did you reject them? – D.W. Feb 16 '16 at 0:34

A basic question is "what is the minimum number of edges (or minimum cost of edges) to be added to the graph $G$ to increase its edge connectivity to a certain value?".