Problem $1.$ Streaming Edges

$1.$ Suppose $\backslash ($ G$=($V$,$ E$)\backslash )$ is an undirected graph with edge weights $\backslash ($ w $\backslash ),$ and suppose you have already computed a min$-$weight spanning tree $\backslash ($ T $\backslash )$ for $\backslash ($ G $\backslash ).$ Suppose a new edge $\backslash ($ e$=($u$,$ v$)\backslash )$ with weight $\backslash ($ w$($e$)\backslash )$ is added to the graph, to obtain a new graph $\backslash ($ G$^\{\backslash$prime$\}\backslash ).$ Show how, given $\backslash ($ G$,$ T$,($u$,$ v$)\backslash )$ and $\backslash ($ w$($e$)\backslash ),$ one can compute a MST $\backslash ($ T$^\{\backslash$prime$\}\backslash )$ for the larger graph $\backslash ($ G$^\{\backslash$prime$\}\backslash )$ in time $\backslash ($ O$($n$)\backslash )$ where $\backslash ($ n $\backslash )$ is the number of nodes in $\backslash ($ G $\backslash ).$ You may assume $\backslash ($ T $\backslash )$ is given as a graph with the same node set as $\backslash ($ G $\backslash ).$

Note: $\backslash ($ O$($n$)\backslash )$ time is not enough to re$-$read the original graph. Your proof of correctness has to explain why it is ok to ignore lots of the edges in $\backslash ($ G $\backslash ).$

$2.$ Now consider a setting where you are given the edges of a graph in a streaming fashion, that is$,$ you get them one at a time and want to process them using very little additional space. Each edge is described by a triple $\backslash (($u$,$ v$,$ w$)\backslash ),$ where $\backslash ($ u $\backslash )$ and $\backslash ($ v $\backslash )$ are vertices and $\backslash ($ w $\backslash )$ is the weight of the edge. The edges are undirected.

Specifically, you have access to a data structure edge$\_$stream that supports the following two operations: has$\_$next$()$ and next$\_$edge$().$ A call to edge$\_$stream.has$\_$next$()$ returns true if there are more edges in the stream and false otherwise. edge$\_$stream.next$\_$edge$()$ returns the next edge in the stream. There is no way to go backwards and re$-$read previous edges. $($If you want to access edges again, you have to store them.$)$ You may assume that the nodes' names are all integers in $\backslash (\backslash \{1,\backslash$ldots$,$ n$\backslash \}\backslash ).$

Your goal is to write an algorithm that computes the minimum$-$weight spanning tree of the graph in this streaming setting. Write an algorithm that, given a set of vertices $\backslash ($ V $\backslash )$ and an edge stream edge$\_$stream, builds a min$-$weight spanning tree of the graph using at most $\backslash ($ O$($n$)\backslash )$ space and $\backslash ($ O$($n $\backslash$cdot m$)\backslash )$ time, where $\backslash ($ m$=|$E$|\backslash )$ is the number of edges in edge$\_$stream. The stream itself does not count against your space budget, but any data structures or additional storage you use do$.[$Hint: Use part $1.]$

An algorithm that uses more than $\backslash ($ O$($n$)\backslash )$ space will get at most half credit.