Let $G = (V, E)$ be a connected weighted graph. Assume the weights are distinct. Let $V_1, V_2, . . . , V_p$ be a partition of V into two or more nonempty parts.
For each $i (1 ≤ i ≤ p)$, let ei be the minimum weight edge within the set of all edges with one endpoint in Vi and the other in $V − V_i$ . Call such an edge a super-edge.
(a) Prove that for each i such a super-edge ei exists.
Define a new graph S whose vertices are the parts $V_i$ (so S has p vertices), and two parts are connected iff there a super-edge between them.
(b) Prove that S is a forest. (c) Prove that S has at most p/2 components.
For problem a, is it because ei contains in the minimum spanning tree? for problem b, I think we should have a cycle whose both edges are super-edge and get contradiction? I have no idea how to do c.
This is a long problem, Could someone help me ?