Problem $2(25$ Points $-$ MST Uniqueness$).$ Throughout the lectures on minimum spanning trees $\backslash (($M S T$)\backslash ),$ we assumed that no two edges in the input graph have equal weights, which implies that the MST is unique. In fact, a weaker condition on the edge weights implies MST uniqueness.

$1.(5$ Points$)$ Describe an edge$-$weighted graph that has a unique minimum spanning tree, even though two edges have equal weights.

$2.(10$ Points$)$ Prove that each of the following two conditions are sufficient for a graph $\backslash ($ G $\backslash )$ to have a unique minimum spanning tree:

$($a$)$ For any partition of the vertices of $\backslash ($ G $\backslash )$ into two subsets, the minimum$-$weight edge with exactly one endpoint in each subset is unique.

$($b$)$ The maximum$-$weight edge in any cycle of $\backslash ($ G $\backslash )$ is unique.

$3.(10$ Points$)$ Describe and analyze an algorithm to determine whether or not a graph has a unique minimum spanning tree.