1) 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 modelled by a connected graph G=(V,E) with n nodes. Each edge e is a fibre-optic cable that is owned by one of the companies –named X and Y and leashed 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 the 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.
Give a polynomial time algorithm, that takes G, with each edge labelled X or Y, and either (i) returns a spanning tree with exactly k edges labelled X, or (ii) reports correctly that no such tree exists.