# Thread: Minimum Cost Spanning Tree

1. ## Minimum Cost Spanning Tree

If a loopless weighted graph (G,W) has a unique edge $\displaystyle e_{m}$ of minimum weight-- that is, $\displaystyle W(e_{m}) < W(e)$ for $\displaystyle e \neq e_{m}$ -- show that any minimum cost spanning tree of G must contain $\displaystyle e_{m}$.

I realize this is true, but I need to prove it. I used Kruskal's Algorithm to show that there is at least one minimal cost spanning tree that includes $\displaystyle e_{m}$. I'm just stuck trying to think of how to prove that edge is in ANY minimal cost spanning tree.

2. I think that you can do it by contradiction.

Suppose that there is a minimum cost spanning tree that does not contain $\displaystyle e_m$. Then, adding $\displaystyle e_m$ to the tree forms a cycle. But if you drop one of the other edges in the cycle, the graph stays connected and is cycle-free (i.e. it is a tree) but has a lower cost than before. This contradicts the minimality of cost. Therefore, any minimum cost spanning tree must contain the edge $\displaystyle e_m$.