Problem $6$: $(16$ points$)$ Consider the following algorithm: Given a weighted undirected graph $G(V,E)($you may assume no two edges in the graph have the same weight.$)$

$E^{\text{'}}$larrE

for each edge einE $in$ decreasing weight order

$ifG(V,E^{\text{'}}-e)is$ still connected then

$,E^{\text{'}}larr{E}^{\text{'}}-e$

return $E^{\text{'}}$

Show that this outputs a Minimum spanning tree correctly. $($By proving the Greedy choice property and the optimal substructure property$).$