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.