Question $1$: $20$ points

You are given a weighted, undirected graph $G=(V,E)$ and a minimum spanning tree $($MST$)$

$T$ of the graph $G.$ Answer the following questions about $G$ and $T.$

$($a$)[10$ points$]$ Suppose we decrease the weight of an edge $e$ where einG and $e!$inT. Let the

new graph be denoted by $G^{\text{'}}.$ Suggest an algorithm, in plain English bullet points, that

checks whether $T$ is an MST of $G^{\text{'}}.$ If not, the algorithm calculates the new MST $T^{\text{'}}$ of

$G^{\text{'}}.$ Also, analyse your algorithm's time complexity.

$($Note: Suggest an algorithm that do not require rerunning Prim's or Kruskal's algorithm$)$

$($b$)[10$ points$]$ Consider the following algorithm's pseudocode. Is it a correct MST algorithm?

If YES, explain why. If NO$,$ explain why. Regardless of the algorithm's correctness,

calculate the time complexity of the algorithm.