Let G = (V, E) be an undirected graph with distinct edge weights w (u, ) on each edge (u, ) E. For each

Let G = (V, E) be an undirected graph with distinct edge weights w (u, ν) on each edge (u, ν) ∈ E. For each vertex ν ∈ V, let max(ν) = max(u,ν) ∈ E {w(u, ν)} be the maximum-weight edge incident on that vertex. Let S_G = {max(ν) : ν ∈ V} be the set of maximum-weight edges incident on each vertex, and let T_G be the maximum-weight spanning tree of G, that is, the spanning tree of maximum total weight. For any subset of edges E′ ⊆ E, define w (E′) = ∑(u,ν)∈ E′ w(u, ν).

a. Give an example of a graph with at least 4 vertices for which S_G = T_G.

b. Give an example of a graph with at least 4 vertices for which S_G ≠ T_G.

c. Prove that S_G ⊆ T_G for any graph G.

d. Prove that w (T_G) ≥ w(S_G)/2 for any graph G.

e. Give an O(V + E)-time algorithm to compute a 2-approximation to the maximum spanning tree.