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 belongs to C be the heaviest edge of C. The the minimum spanning tree of G does not contain e.

(b) Given an edge e belongs to 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 of G, and G1 = (E1, V1), where E1 = E \ {e}, then the MST of G1 is also an MST of G. 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 algorithm's correctness and prove that its runtime meets this requirement. Hint: start by sorting the edges in descending order of weight.