Let G := (V, E) be a graph with positive edge lengths ce for all edges e E E. Recall that for a set of vertices S CV, the cut 8(S) CE is the set of all edges in G with exactly one end-point in S. Consider the following IP (II) over the variables (Xe : e E): min CEE such that > 1 for all S{0,V} e E(S) Xe & {0, 1} for all e EE (a) Write the corresponding IP for the following graph, where each edge is labeled by its length. Note that the constraints corresponding to a subset S and its complement S are the same. Write each distinct constraint only once. (b) Suppose a is a feasible solution to the IP (II), and Ti is the set of edges with characteristic vector a, i.e., an edge e E Tiff de = 1. Verify that for any superset T2 E of T, the characteristic vector b of T2 is also feasible for (II), and that the objective function value of b is at least as large as that of a. (c) List all the minimal subsets of edges T corresponding to feasible solutions for the IP derived in Part (a), where we say that T is minimal if no proper subset of T corresponds to a feasible solution. Hence find an optimal solution to the IP. (d) Prove that the IP (II) is feasible if and only if there is a u, v-path in G for every pair of distinct vertices u. V EV. Let G := (V, E) be a graph with positive edge lengths ce for all edges e E E. Recall that for a set of vertices S CV, the cut 8(S) CE is the set of all edges in G with exactly one end-point in S. Consider the following IP (II) over the variables (Xe : e E): min CEE such that > 1 for all S{0,V} e E(S) Xe & {0, 1} for all e EE (a) Write the corresponding IP for the following graph, where each edge is labeled by its length. Note that the constraints corresponding to a subset S and its complement S are the same. Write each distinct constraint only once. (b) Suppose a is a feasible solution to the IP (II), and Ti is the set of edges with characteristic vector a, i.e., an edge e E Tiff de = 1. Verify that for any superset T2 E of T, the characteristic vector b of T2 is also feasible for (II), and that the objective function value of b is at least as large as that of a. (c) List all the minimal subsets of edges T corresponding to feasible solutions for the IP derived in Part (a), where we say that T is minimal if no proper subset of T corresponds to a feasible solution. Hence find an optimal solution to the IP. (d) Prove that the IP (II) is feasible if and only if there is a u, v-path in G for every pair of distinct vertices u. V EV