Let G $=($V$,$ E$)$ be a connected graph with a weight function w : E R$,$ and let T be a minimumspanning tree $($MST$)$ for G$.$ Suppose a new edge e is added to the graph, where e $/$ E$.$Design an algorithm to efficiently compute the new minimum spanning tree for the updatedgraph G $=$ G $\{$e$\}\mathrm{.}1.$ Describe $($in words$)$ your algorithm $($to a degree where someone could implement it if givenyour answer$).$Solution:$2.$ Argue why your algorithm is correct, meaning given any input, why does your algorithmproduce the correct outputs? Justify your answer.Solution:$3.$ Analyze the runtime of your algorithm. Justify your answer.

Let $G=(V,E)$ be a connected graph with a weight function $w$:$ER,$ and let $T$ be a minimum

spanning tree $($MST$)$ for $G.$ Suppose a new edge $e^{\text{'}}$ is added to the graph, where $e^{\text{'}}!$inE.

Design an algorithm to efficiently compute the new minimum spanning tree for the updated

graph $G^{\text{'}}=G\{e^{\text{'}}\}.$

Describe $($in words$)$ your algorithm $($to a degree where someone could implement it if given

your answer$).$

$$i

Argue why your algorithm is correct, meaning given any input, why does your algorithm

produce the correct outputs? Justify your answer.

Analyze the runtime of your algorithm. Justify your answer.