Professor Olivier suggests the following algorithm for finding a minimum spanning tree in a given connected graph G = (V,E) with edge weights w(e).

Notice that q(u) is the sum of weights of all edges incident to vertex u. (a) Show that this algorithm does not always return a minimum spanning tree.

(b) Does it always return a tree?

begin for every u E V do Sort Vn ncreasing for i 1 to n do 1U( :V :ut)( :/.11, (U.'V by q(v) into v,. . . ,Vn e_a lightest edge incident to vi Lreturn (V,T)