URGENT!! Consider a weighted, connected, undirected graph G = (V,E) where all edge weights are distinct. Note that, as edge weights are distinct, G has a unique minimum spanning tree.

(a) Prove the following property about G. Let C be any cycle in G, and let e C be the heaviest edge of C. The the minimum spanning tree of G does not contain e.

(b) Given an edge e E, devise an O(|V | + |E|) algorithm to check if e appears in a cycle of G. Hint: make a minor modification to G and use a well-known algorithm.

c) Your proof for part (a) implies the following property: if e is the heaviest edge in a cycle ofG,andG1 =(E1,V1),whereE1 =E\{e},thentheMSTofG1 isalsoanMSTofG. Devise an algorithm that uses this property and your algorithm from part (b) to find an MST of G in O(|E|2) time. Justify your algorithms correctness and prove that its runtime meets this requirement.

Hint: start by sorting the edges in descending order of weight.