**Spanning Trees:**

The k-Spanning Tree problem takes as input an undirected graph Gand produces as output a spanning tree of G in which every node hasdegree ≤ k (if such a tree exists).

In this problem you will prove that, for any k ≥ 2, thek-Spanning Tree problem is NP complete.

(1)

Suppose that you have an undirected graph G and are given aproposed solution for the k-Spanning Tree problem for some value ofk ≥ 2. In two or three precise sentences, explain what you wouldhave to do to verify the proposed solution.

(2)

The 2-Spanning Tree problem is identical to the Rudrata Pathproblem, which is known to be NP complete.

Let’s reduce the 2-Spanning Tree problem to the 3-Spanning Treeproblem. The first step in the reduction is to convert a graph G,intended as input to the 2-Spanning Tree problem, into a graphf(G), intended as input to the 3-Spanning Tree problem.

It is possible to design a correct f(G) that operates byapplying a simple operation to each vertex of G. In one sentence,explain what this operation is.

(3)

The second step in the reduction is to convert a 3-spanning treeT for f(G) into a 2-spanning tree h(T) for G.

It is possible to design a correct h(T) that operates byapplying a simple operation to each vertex of T. In one sentence,explain what this operation is.

(4)

You have just proven that the 3-Spanning Tree problem is NPcomplete. In two or three precise sentences, explain how you wouldprove that the k-Spanning Tree problem is NP complete for all k ≥2.

## Expert Answer

Answer to Spanning Trees: The k-Spanning Tree problem takes as input an undirected graph G and produces as output a spanning tree …