For problems that require you to provide an algorithm, you must give the

following:

1. a precise description of the algorithm in English and, if helpful, pseudocode,

2. a proof of correctness,

3. an analysis of running time and space

1. (a) Prove that if the edge costs of a connected graph G are all distinct, the minimum spanning tree of G is unique. (b) Consider two graph G and G': G is a connected graph with edge costs. The edge costs of G are either 1 or 2. And G is constructed by copying G and deleting all the edges with . Let n be the number of vertices of G, and c be the number of the connected component Provide an efficient algorithm which outputs a minimum spanning tree for a connected of G'. Prove that the cost of the minimum spanning tree of G is n-1c-1 graph with edge costs either 1 or 2. The runnung time of the algorithm should be linear to the number of vertices and edges