In particular, you can assume that there is an algorithm FindPath that, given an undirected graph G and two spanning trees T and T' of G, efficiently returns to you a path (namely an ordered list of spanning trees of G) from T to T' in H. (2) Note that if T and T'are neighbors in H, then the number of X-edges in T can differ from the number of X-edges in T' by at most one. (3) You should find a spanning tree of G that contains the minimum possible number a of X-edges, and also a spanning tree of G that contains the maximum possible number b of X-edges.)

28. Suppose you're a consultant for the networking company CluNet, and they have the following problem. The network that they're currently working on is modeled by a connected graph G=(V,E) with n nodes. Each edge e is a fiber-optic cable that is owned by one of two companies- creatively named X and Y-and leased to CluNet. Their plan is to choose a spanning tree T of G and upgrade the link:s corresponding to the edges of T. Their business relations people have already concluded an agreement with companies X and Y stipulating a number k so that in the tree T that is chosen, k of the edges will be owned by X and n -k-1 of the edges will be owned by Y. CluNet management now faces the following problem. It is not at all clear to them whether there even exists a spanning tree T meeting these conditions, or how to find one if it exists. So this is the problem they put to you: Give a polynomial-time algorithm that takes G, with each edge labeled X or Y, and either (i) returns a spanning tree with exactly k edges labeled X, or (ii) reports correctly that no such tree exists. 28. Suppose you're a consultant for the networking company CluNet, and they have the following problem. The network that they're currently working on is modeled by a connected graph G=(V,E) with n nodes. Each edge e is a fiber-optic cable that is owned by one of two companies- creatively named X and Y-and leased to CluNet. Their plan is to choose a spanning tree T of G and upgrade the link:s corresponding to the edges of T. Their business relations people have already concluded an agreement with companies X and Y stipulating a number k so that in the tree T that is chosen, k of the edges will be owned by X and n -k-1 of the edges will be owned by Y. CluNet management now faces the following problem. It is not at all clear to them whether there even exists a spanning tree T meeting these conditions, or how to find one if it exists. So this is the problem they put to you: Give a polynomial-time algorithm that takes G, with each edge labeled X or Y, and either (i) returns a spanning tree with exactly k edges labeled X, or (ii) reports correctly that no such tree exists