# Upper Bound on Local Search MST Consider a connected weighted graph $$G=(V,E)$$. The local search algorithm is used to find the Minimum Spanning Tree, only swapping one edge for another at a time. At each step of the local search algorithm, select the best improving swapping of edges: $$\{e, f\}$$, where $$w_f – w_e$$ is maximized.

Here is how the algorithm works:

Define a spanning tree $$T$$ in $$G$$. Let $$e$$ be an edge in $$G \setminus T$$, and define $$C$$ as the cycle created when $$e$$ is added to $$T$$. If $$w_e < w_f$$, where $$f$$ is the edge in $$C \setminus \{e\}$$ of largest weight, then $$\{e, f\}$$ is defined as an improving swap and we set $$T := (T \setminus f) ∪ e$$. We repeat this until there are no more improving swaps.

There exists a finite number of spanning trees in a graph $$G$$. So, when using the best improving swap local search algorithm, there must be an eventual termination of the algorithm in a finite number of steps since the weight of the spanning tree falls in each step.

What I need is an upper bound on the max number of steps the best improving swap local search algorithm will take. Assume every edge weight in the $$G$$ is distinct.

I’m really stuck and I’m not sure how to even start this problem, any help would be appreciated. 