Exercise 2: Cycle Property (25 Points)
Assume an undirected, weighted, connected graph. The cycle property states that the largest
weight edge of any cycle does not belong to an MST of the graph.
1. Prove the cycle property.
2. Describe an algorithm to output the MST of a graph using the cycle property.
3. Give an implementation of your algorithm and analyze its run time.