Given a graph with n + 1 nodes, a K-tree is defined to be a set of n + K edges that span the graph. This paper presents an algorithm for finding a minimum cost K-tree with a specified degree at a designated node. The algorithm runs in O(n3) time and is useful in the optimal solution of certain Lagrangian relaxations arising in vehicle routing.