Decide whether you think the following statement is true or

Decide whether you think the following statement is true or false. If it is true, give a short explanation. If it is false, give a counterexample. Let G bean arbitrary connected, undirected graph with a distinct cost c(e) on every edge e. Suppose e* is the cheapest edge in G; that is, c(e*)*. Then there is a minimum spanning tree T of G that contains the edge e*.

Solution

Answer is true. Minimum spanning tree T of G always contains the cheapest edge.

Suppose we are running kruskal\'s algorithm for finding minimum spanning tree, then we first sort all the edges according to their cost, then we are adding edges one by one in the sequence from the low cost edge to higher cost edge. All the edges are distinct, hence we always add the cheapest edge first in the spanning tree.