$1$ Boruvka$$s Algorithm $(40$ points$)($a$)(10$ points$)$ This was stated in class, but let$$s prove it formally. Let G $=($V$,$ E$)$ be an undirected graph and let w : E $$ R$0$ be edge weights. Prove that if all edge weights are distinct $($w$($e$)=$ w$($e $)$ for all e $=$ e $$ in E$)$ then there is a unique minimum spanning tree $($MST$).$ Let G $=($V$,$ E$)$ be a connected, undirected graph and let w : E $$ R$0$ be distinct edge weights $($w is injective$).$ We$$re going to analyze yet another MST algorithm: Boruvka$$s MST algorithm $($from $1926),$ which is a bit like a distributed version of Kruskal. We begin by having each vertex mark the lightest edge incident to it$.($For instance, if the graph were a $4-$cycle with edges of lengths $1,3,2,$ and $4$ around the cycle, then two vertices would mark the $1$ edge and the other two vertices will mark the $2$ edge$).$ This creates a forest F of marked edges. $($Convince yourself that there won$$t be any cycles!$).$ In the next step, each tree in F marks the shortest edge incident to it $($the shortest edge having one endpoint in the tree and one endpoint not in the tree$),$ creating a new forest F $.$ This process repeats until we have only one tree. $($b$)(10$ points$)$ Show correctness of this algorithm by proving that the set of edges in the current forest is always contained in the MST$.($c$)(10$ points$)$ Show how you can run each iteration of the algorithm in O$($m$)$ time with just a few runs of DFS and no fancy data structures $($heaps$,$ union$-$find $$ remember, this algorithm was from $1926!).$ In other words, given a current forest F of marked edges, show how to find the set of edges which consists of the shortest edge incident to each tree in F in time O$($m$).($d$)(10$ points$)$ Prove an upper bound of O$($m log n$)$ on the running time of this algorithm $1$ Boruvka's Algorithm $(40$ points$)$

$($a$)(10$ points$)$ This was stated in class, but let's prove it formally. Let $\backslash ($ G$=($V$,$ E$)\backslash )$ be an undirected graph and let $\backslash ($ w: E $\backslash$rightarrow $\backslash$mathbb$\{$R$\}\_\{\backslash$geq $0\}\backslash )$ be edge weights. Prove that if all edge weights are distinct $\backslash (\backslash$left$($w$($e$)$

eq w$\backslash$left$($e$^\{\backslash$prime$\}\backslash$right$)\backslash$right$.\backslash )$ for all $\backslash (\backslash$left$.$e

eq e$^\{\backslash$prime$\}\backslash$in E$\backslash$right$)\backslash )$ then there is a unique minimum spanning tree $($MST$).$

Let $\backslash ($ G$=($V$,$ E$)\backslash )$ be a connected, undirected graph and let $\backslash ($ w: E $\backslash$rightarrow $\backslash$mathbb$\{$R$\}\_\{\backslash$geq $0\}\backslash )$ be distinct edge weights $(\backslash ($ w $\backslash )$ is injective$).$ We're going to analyze yet another MST algorithm: Boruvka's MST algorithm $($from $1926),$ which is a bit like a distributed version of Kruskal.

We begin by having each vertex mark the lightest edge incident to it$.($For instance, if the graph were a $4-$cycle with edges of lengths $\backslash (1,3,2\backslash ),$ and $4$ around the cycle, then two vertices would mark the $"1"$ edge and the other two vertices will mark the $"2"$ edge$).$ This creates a forest $\backslash ($ F $\backslash )$ of marked edges. $($Convince yourself that there won't be any cycles!$).$ In the next step, each tree in $\backslash ($ F $\backslash )$ marks the shortest edge incident to it $($the shortest edge having one endpoint in the tree and one endpoint not in the tree$),$ creating a new forest $\backslash ($ F$^\{\backslash$prime$\}\backslash ).$ This process repeats until we have only one tree.

$($b$)(10$ points$)$ Show correctness of this algorithm by proving that the set of edges in the current forest is always contained in the MST$.$

$($c$)(10$ points$)$ Show how you can run each iteration of the algorithm in $\backslash ($ O$($m$)\backslash )$ time with just a few runs of DFS and no fancy data structures $($heaps$,$ union$-$find $-$ remember, this algorithm was from $1926!).$ In other words, given a current forest $\backslash ($ F $\backslash )$ of marked edges, show how to find the set of edges which consists of the shortest edge incident to each tree in $\backslash ($ F $\backslash )$ in time $\backslash ($ O$($m$)\backslash ).$

$($d$)(10$ points$)$ Prove an upper bound of $\backslash ($ O$($m $\backslash$log n$)\backslash )$ on the running time of this algorithm.