A constrained minimum spanning tree problem

In the classical general framework of the minimum spanning tree problem for a weighted graph we consider the case in which a predetermined vertex has a certain fixed degree. In other words, given a weighted graph G, one of its vertices v0 and a positive integer k, we consider the problem of finding the minimum spanning tree of G in which the vertex v0 has degree k, that is the number of edges coming out of v0. We recall that among the various methods for the solution of the unconstrained problem an efficient way to find the minimum spanning tree is based on the simple procedure of choosing one after the other an edge of minimum weight that has not be chosen yet and does not create cycles if added to the previously chosen edges. This technique is known as the “greedy algorithm”. There are problems for which the greedy algorithm works and problems for which it does not. We prove that for the solution of the one degree constrained minimum spanning tree problem the classical greedy algorithm finds a right solution.