Alternative Minimum Spanning Trees $(23\mathrm{.}4$ CLRS$).(20$ points$)$ In this problem,

we give pseudocode for two different algorithms. Each one takes a connected graph and

a weight function as input and returns a set of edges T$.$ For each algorithm, either show

that $T$ is a minimum spanning tree $($give a brief justification of the algorithm$)$ or show

that $T$ is not a minimum spanning tree $($give a counter$-$example$).$

a$.(10$ points$)$ MAYBE$-$MST$-$A $(G,w)$

sort the edges into non$-$increasing order of edge weights $w$

$T=E$

for each edge einE, taken in non$-$increasing order by weight

if $T-\{e\}$ is a connected graph

$T=T-\{e\}$

return $T$

b$.(10$ points$)$ MAYBE$-$MST$-$B $(G,w)$

$T=$ null

for each edge $e,$ taken in arbitrary order

if $T\{e\}$ has no cycles

$T=T\{e\}$

return $T$