Finding a New Minimum Spanning Tree After a New Edge Was Added to The Graph

Question

Let G = (V, E) be a weighted, connected and undirected graph and let T be a minimum spanning tree. Let e be any edge not in E (and has a weight W(e)). Prove or disprove: T U {e} is an edge set that contains a minimum spanning tree of G' = (V, E U {e}).

Well, it sounds true to me, so I decided to prove it but I just get stuck every time...

For example, if e is the new edge with minimum weight, who can promise us that the edges in T weren't chosen in a bad way that would prevent us from obtaining a new minimum weight without the 'help' of other edges in E - T ?

I would appreciate any help, Thanks in advance.

Ewold

Answer 1

Let [a(1), a(2), ..., a(n-1)] be a sequence of edges selected from E to construct MST of G by Kruskal's algorithm (in the order they were selected - weight(a(i)) <= weight(a(i + 1))).

Let's now consider how Kruskal's Algorithm behaves being given as input E' = E U {e}. Let i = min{i: weight(e) < weight(a(i))}. Firstly algorithm decides to choose edges [a(1), ..., a(i - 1)] (e hasn't been processed yet, so it behaves the same). Then it need to decide on e - if e is dropped, solution for E' will be the same as for E. So let's suppose that first i edges selected by algorithm are [a(1), ..., a(i - 1), e] - I will call this new sequence a'. Algorithm continues - as long as its following selections (for j > i) satisfy a'(j) = a(j - 1) we are cool. There are two scenarios that break such great streak (let's say streak breaks at index k + 1):

1) Algorithm selects some edge e' that is not in T, and weight(e') < weight(a(k+1)). By now a' sequence is:

[a(1), ..., a(i-1), e, a(i), a(i+1), ..., a(k-1), a(k), e']

But if it was possible to append e' to this list it would be also possible to append it to [a(1), ..., a(k-1), a(k)]. But Kruskal's algorithm didn't do it when looking for MST for G. That leads to contradiction.

2) Algorithm politely selected:

[a(1), ..., a(i-1), e, a(i), a(i+1), ..., a(k-1), a(k)]

but decided to drop edge a(k+1). But if e was not present in the list algorithm would decide to append a(k+1). That means that in graph (V, {a(1), ..., a(k)}) edge a(k+1) would connect the same components as edge e. And that means that after considering by algorithm edge a(k + 1) in case of both G and G' the division into connected components (determined by set of selected edges) is the same. So after processing a(k+1) algorithm will proceed in the same way in both cases.

Ignoble

Wow, I am shocked! I never received such a detailed and informative response. Your proof is excellent and it helped me a great deal! Thanks !!! – Ewold

Answer 2

When ever a edge is add to a graph without adding a node , then that edge creates a cycle in minimum spanning tree of graph, cycle length may vary from 2 to n where n= no of nodes in graph. T = Minimum spanning tree of G Now to find the MST for (T + added edge) , we have to just remove one edge from that cycle .. so remove that edge which has maximum weight.

So T' always comes from T U {e}.

And if you are thinking that this doesn't prove that new MST will be an edge set of T U {e} then analyse Kruskal algorithim for for new graph. i.e. if e is of minimum weight it must have been selected for MST acc to Kruskal algorithim and same here if it is minimum it can not be removed from cycle.

Carte

I didnt get you..in MST all vertices will be there ...its about choosing edges. – Carte

That's a typo, let me re-state the question: How can you prove that when edge e is added (in Kruskal algorithm), it doesn't cause 2 or more edges in set T to be impossible to be chosen? – City

question is about proving that the edges of new MST T' will be a subset of edges of T + {e}...so adding a edge will obviously cause an edge to be removed ..and that "edge" can be any edge even the edge added. but if added edge is of minimum weight..it will be there in new MST for sure. – Carte

The talk about edge set (your 2nd paragraph) is actually off the point. You need to prove that T' is an MST for the graph G U {e} (T' is indeed MST of T U {e}, but it doesn't mean that it is clearly the MST of G U {e}). – City

if T' is the MST of T U {e} then it will be the MST of G U {e} because all the other edges that are in G U {e} will be of higher weights as T is itself have all the eligible minimum edges of G. – Carte

The original T doesn't contain all the minimum edges of G. Only the sum of the edges is guaranteed. – City