Consider the Minimum Spanning Tree Problem on an undirected

Consider the Minimum Spanning Tree Problem on an undirected graph G=(V,E), with a cost ce 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.

Solution

Minimum Spanning Tree: A minimum spanning tree is a subset of edge weighted undirected graph
which contains all the vertices of the spanning tree connected to one another without forming cycles
through edges and whose sum of wieghts should be as minimum as possible.

There are few properties of minimum spanning tree among which two of them are:
1. Minimum-cost Subgraph: By this property we mean that if the edge weighted undirected graph
consists of all positive weights then the minimum spanning tree must be the subgraph connecting all
vertices with lowest cost.
2. Minimum-cost Edge- By this property we mean that if all the weights of the tree are unique then we
determine the tree with the lower incurred cost. But if all the weights of the edges are not unique then we
remove the edges constituting the larger weights until we get a spanning tree of minimum weight.

Let G be a graph, T be a spanning tree, E be the edge set and e be the edge with minimum cost.
If e is the edge with unique positive weight then this edge is included in minimum spanning tree such that
e belongs to T which is a minimum spanning tree of graph G and if e is not the edge with unique positive
weight then we remove all the edges, e belongs to E until we get the edge with minimum cost such that
e is the edge in the minimum spanning tree.
Hence, from this we can proove that for minimum spanning tree to be formed out of graph the tree itself has to
be minimum.