Given a connected undirected graph G, a spanning tree is a connected subgraph that is a tree and inc ...

---

Given a connected undirected graph G, a spanning tree is a connected subgraph that is a tree and includes all the vertices of G. Consider the following variant of the spanning tree problem: given a connected undirected graph G, decide whether there exists a spanning tree in which every node has degree at most five. Show that this problem is NP-hard. (Hint: try a reduction from the Hamiltonian cycle problem, but it is easier to go in two steps. First reduce Hamiltonian cycle to Hamiltonian path, then reduce Hamiltonian path to the spanning tree problem. For the second reduction, suppose V is the vertex set of the Hamiltonian path instance; for each vertex v in V, create three additional vertices and put edges between these new vertices and v.)