(6 points) In this problem we'll see how strong duality, which is critical in single-commodity flow, breaks down in multi-commodity flow. In multi-commodity flow our basic input is (V, C, $1, t1, di, . .., SK, th, dk) where each s; or t; is a vertex in V (there may be repetitions in the list), and each di is some nonnegative demand. The meaning of the edge capacities Guy is that Cus bounds the total of all commodities flowing across edge (u, v) in either direction. We say the input is feasible if there are flows fl, ..., f* which ship quantity di of flow from si to ti for each i, and which in combination respect the edge capacities. More carefully, this means that each f is an si-ti flow (in the single-commodity sense, so f' has flow conservation everywhere except at s; and ti), and that for each (u, v), we have Ei Ifuul Cs, SC. (b) (Failure of strong duality) By appropriately choosing demands and capacities for the following network, show that the input may be infeasible even if for all cuts (S, SC), Ds,sc