35-6 Approximating a maximum spanning tree

Let $G = (V, E)$ be an undirected graph with distinct edge weights $w(u, v)$ on each edge $(u, v) \in E$. For each vertex $v \in V$, let $\max(v) = \max_{(u, v) \in E} \{w(u, v)\}$ be the maximum-weight edge incident on that vertex. Let $S_G = \{\max(v): v \in 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' \subseteq E$, define $w(E') = \sum_{(u, v) \in E'} w(u, v)$.

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 \ne T_G$.

c. Prove that $S_G \subseteq T_G$ for any graph $G$.

d. Prove that $w(T_G) \ge 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.

(Omit!)