We are given an undirected graph G = (V, E) and we want to decide if there exists a spanning tree T of G where every ver

[correctanswer]

We Are Given An Undirected Graph G V E And We Want To Decide If There Exists A Spanning Tree T Of G Where Every Ver 1 (191.84 KiB) Viewed 124 times

We are given an undirected graph G = (V, E) and we want to decide if there exists a spanning tree T of G where every vertex has degree at most 4. In particular, each vertex should be incident to at most 4 edges in T. Your task is to prove that the above problem is NP-complete. (a) Show that the problem belongs to the class NP. (b) Prove that the problem is NP-hard. [Hint: Reduce from the Hamiltonian Path problem: Given a graph H (V', E'), decide if there is a simple path that visits all vertices.] -