Hi guys,

I have done some thinking about how to solve 2nd best Minimum Spanning Tree. I want to hear your suggestions on if its correct and how you would solve it. Thanks.

Let G = (V,E) be a graph. Lets assume we know how to solve the MST using Kruskal as that is trivial. At each step of Kruskal, consider an edge e=<a,b>.

If e does not cause a cycle then it is in MST Otherwise It can cause a cycle. Now consider all edges in such a cycle and take the biggest edge in the cycle e1.

Claim : If we maintain the value (e-e1) and minimize it over all cases where adding an edge will introduce a cycle then we would have the 2nd best MST by simply replacing e1 with e.

Is this true ? How would you solve this problem ?

Thanks.