Let G = (V, E) be a connected, undirected graph. For each edge e ∈ E, we have a cost weight ce. The minimum-spanning-tree problem is to find an acyclic subset T ⊆ E that connects all of the vertices and whose total weight c(T ) = ô°€e∈T ce is minimized.
1. Formulate this problem as a linear program. Show the correctness of your formulation.
2. Write down the dual of your LP formulation.