Let's consider linear programming formulations of the minimum spanning tree problem. We now have an (undirected) graph G = (V, E) and weights w : E R+. As we discussed in class, one way of phrasing the minimum spanning tree problem is as finding the minimum cost connected subgraph which spans all nodes. This interpretation naturally gives rise to a straightforward LP relaxation which requires every cut to have at least one edge crossing it (fractionally). More formally, suppose that we have a variable xe for every edge e, and consider the following linear program. For all S V , let E(S, S) denote the edges with exactly one endpoint in S and exactly one endpoint not in S. minX eE w(e)xe subject to X eE(S,S) xe 1 S V : S 6= xe 0 e E Note that there are an exponential number of constraints, but let's not worry about that