This problem is about the minimum spanning tree (MST) problem in an undirected graph, where every edge has a non-negative cost.
(a) Write an LP for the MST problem, which enforces the constraint that at least one edge is selected from every cut. Show that you can solve this LP in polynomial time by using an efficient separation oracle.
(It is sufficient to identify the problem you need to solve in the separation oracle; you do not need to give an explicit algorithm.)
Give an example to show that this LP is not integral. (Recall that an LP is said to be integral if there is at least one optimal solution where all the variables take integer values.)
(b) Write a different LP for the MST problem where you enforce an upper bound on the number of edges selected from any induced subgraph, and a lower bound on the total number of edges. Show that any integral feasible solution to this LP is a spanning tree of the graph.