Instead of adding edges, we propose a new algorithm for solving the Minimum Spanning Tree problem by removing

edges:

Let G $=($V$,$ E$)$ be a graph where edge i has weight wi$.$ Call an edge e $$unnecessary$$ if removing e would not cause

the graph to be disconnected.

Consider the following greedy algorithm:

function Laksurks$-$Algorithm$($Graph G$)$

Sort edges in decreasing order of weight

for each edge e in decreasing order do

if e is unnecessary then

delete e

return remaining edges, which are an MST$.$

$($a$)$ Prove that if G is a connected graph, then Laksurk$$s Algorithm produces a spanning tree $($don$$t worry about

minimum yet!$)$

$($b$)$ Prove that if G is a connected graph with distinct edge weights, then Laksurk$$s Algorithm produces the mini$-$

mum spanning tree. You may use as a fact that since the edge weights are distinct, the MST is unique.