Proofs for minimum spanning trees

Please show me the detailed solutions - see the attached file, thank you.

a) Prove the following property for Minimum Spanning Trees: Suppose we are given a graph G with distinct edge weights. Suppose further that G has a cycle C and let c be the maximum weight edge belonging to C. Then c does not belong to any MST.

b) Suppose we have already computed the minimum spanning tree T of an undirected graph G = (V,E). Then, suppose a new edge (u, v), not already in E, is inserted into G (vertices u and v are already in V, so the number of vertices stays the same). Show how to compute the new MST by using T. This is to be done in O(|V|) time by going through steps that include doing a depth first search. You may assume that all edge weights are distinct. If necessary, you may use results proven in parts (a) of this question.

c) We have seen two greedy algorithms for MST. Here is a divide and conquer algorithm for finding MST of a graph G: Divide V(G) to two arbitrary subsets V1 and V2 so that |V1| = [|V(G)|/2] and there is at least one edge between V1 and V2 in G. Recursively compute the MST of G[V1] and G[V2] (induced subgraphs of G on V1 and V2). Let T1 and T2 be the corresponding MSTs. Find an edge c of minimum weight between V1 and V2. Connect T1 and T2 using e and return the resulting tree T. Does this algorithm work, i.e., does it always give a minimum spanning tree? Prove its correctness or provide a counter-example.

d) Let G be an undirected weighted graph such that all edges have the same weight. Provide an algorithm that finds a MST of G in O(n+m) time.