Question

Problem 3: Bounded-Degree Spanning Trees (10 points). Recall the minimum spanning tree problem studied in class. We define a variant of the problem in which we are no longer concerned with the total cost of the spanning tree, but rather with the maximum degree of any vertex in the tree. Formally, given an undirected graph G = (V,E) and T ⊆ E, we say T is a k-degree spanning tree of G if T is a spanning tree of G, and moreover each v ∈ V has degree at most k in T (i.e., v has at most k neighbors in T).

Show that for every fixed constant k ≥ 2, deciding whether G has a k-degree spanning tree is NP-complete. You may reduce from the NP-complete undirected Hamiltonian path problem, defined next. For an undirected graph G = (V, E), we say a path P in G is a Hamiltonian path if it visits each vertex v ∈ V exactly once. The undirected Hamiltonian path problem asks whether a given undirected graph G has a Hamiltonian path.

2

Note. You have already seen the directed variant of the Hamiltonian path problem in the book. Both variants are NP-complete.

Hint. You might want to start with the special case of k = 2.