As given in Exercise 2.5, in the Steiner tree problem we are given an undirected graph G = (V, E) and a set of terminals T V .

As given in Exercise 2.5, in the Steiner tree problem we are given an undirected graph G = (V, E) and a set of terminals T ⊆ V . A Steiner tree is a tree in G in which all the terminals are connected; a non-terminal need not be spanned. Show that the local search algorithm of Section 2.6 can be adapted to find a Steiner tree whose maximum degree is at most 2 OPT +⌈log2 n⌉, where OPT is the maximum degree of a minimum-degree Steiner tree.