# MST Proof (Kleinburg & Tordos)

Consider the Minimum Spanning Tree Problem on an undirected graph G = (V, E), with a cost ≥ 0 on each edge, where the costs may not all be different. If the costs are not all distinct, there can in general be many distinct minimum-cost solutions. Suppose we are given a spanning tree T ⊆ E with the guarantee that for every e ∈ T, e belongs to some minimum-cost spanning tree in G. Can we conclude that T itself must be a minimum-cost spanning tree in G? Give a proof or a counterexample with explanation.

Here is the simplest counterexample. The edge set $$\{10, 12\}$$ is not a minimum spanning tree (MST). However, edge 10 is in the edge set $$\{10, 02\}$$, an MST. Edge 12 is in the edge set $$\{12, 02\}$$, an MST.

Note that there are two edges of equal weight in the above counterexample.

(Question.) What if no edges have the same weight?

Consider the following non-minimum spanning tree.

1
+-------------------+
|                   |
|                   |
|                   |
2|←                 →|2
|                   |
|                   |
|         ↓         |
+-------------------+
1
• Could you please elaborate? – csGeek Dec 5 '18 at 23:51