Suppose youre a consultant for the networking company CluNet, and they have the following problem. The network that theyre 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 Yand leased to CluNet. Their plan is to choose a spanning tree T of G and upgrade the links 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 byX andnk1oftheedgeswillbeownedbyY. 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.

(Hint: (1) 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.)