Question $2(25$ Points$)$:Let G $=($V$,$E$)$ be an undirected, connected graph with real$-$valued weights such that $|$E$||$V$|$ and all edge values are distinct.We define a second$-$best minimum spanning tree as follows. Let T be the set of all spanning trees in G and let I be a minimum spanning tree of G$.$ Then a second$-$best minimum spanning tree is aspanning tree I$\text{'}$ where T$\text{'}$ E $\{$T T$\}$ such that w$($T$\text{'})=$ min$($w$\{$T$\backslash$T$\})($where w is the function thatcalculates the total sum of the edges in a tree$).($a$)(5$ points$)$ Prove that the minimum spanning tree is unique, but that the second$-$best minimum spanning tree need not be unique.$($b$)(10$ points$)$ Let I be the minimum spanning tree of G$.$ Prove that G contains some edge $($u$,$ v$)$ T and some edge $($x$,$ y$)$ T such that $($T $|\{($u$,$ v$)\})$ U $\{($x$,$ y$)\}$ is a second$-$best minimum spanning tree of G $($Hint: remember that a cut in a graph is a partition of vertices into two disjoint sets and an edge is called light if it is the edge with the smallest weight that crosses the cut. You may also refer to the following lemma from class: Suppose there's a minimum spanning tree for graph G containing S where S is a set of edges. Consider a cut that respects S and let $($u$,$ v$)$ be a light edge. Then there is a minimum spanning tree of G containing $\{$SU $($u$,$ v$)\}).($c$)(5$ points$)$ Extra Credit $($Optional$)$: Describe an O$($V$2)$ Dynamic Programming algorithm that, given any spanning tree I of graph G$,$ computes max$|$u$,$ v$],$ for all u$,$ v e V$,$ where max$|$u$,$ vi denotes an edge of maximum weight on the unique simple path between u and v in T$.$ Note: a simple path is a path that does not have repeating vertices. $($Hint: Assume you have access to a function called LCA$($v$,$ w$)$ that finds the lowest common ancestor of two nodes in O$($V$)$ time, where the lowest common ancestor of some nodes v and w in a tree is defined as the deepest node in the tree that has both v and w as descendants$).($d$)(10$ points$)$ Give an efficient algorithm to compute the second$-$best minimum spanning tree of G and calculate the runtime in Big$-$O notation $(5$ points Extra Credit $($Optional$)$: use the algorithm in part c above as part of your solution$).$