Let's consider linear programming formulations of the minimum spanning tree problem. We now have an (undirected) graph G = (V, F) 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 z. for every edge e, and consider the following linear program. For all S c V,let E(S,S) denote the edges with exactly one endpoint in S and exactly one endpoint not in S. min Z w(e)ze ecE subject to z P VSCcV:8#0 e E(5.5) B >t Veec E Note that there are an exponential number of constraints, but let's not worry about that. (a) (25 points) Prove that the optimal value of this LP is at most the weight of the minimum spanning tree. (b) (25 points) Unlike the examples in class, this is not an exact formulation of the MST problem. Find a graph G = (V, E) and weights w : E R such that the optimal LP value is strictly less than the weight of the MST (and prove this)