Incremental Network Design with Minimum Spanning Trees

Given an edge-weighted graph $G=(V,E)$ and a set E₀⊂ E, the incremental network design problem with minimum spanning trees asks for a sequence of edges e'₁,…,e'T∈ E E₀ minimizing ∑ₜ₌₁Tw(Xₜ) where w(Xₜ) is the weight of a minimum spanning tree Xₜ for the subgraph (V,E₀∪'₁,…,e'ₜ\) and T= E E₀. We prove that this problem can be solved by a greedy algorithm.