Problem 4 [20 marks] We are given an undirected graph G = (V, E) and we want to decide if there exists a spanning tree T

[correctanswer]

Problem 4 20 Marks We Are Given An Undirected Graph G V E And We Want To Decide If There Exists A Spanning Tree T 1 (75.81 KiB) Viewed 55 times

Problem 4 [20 marks] 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.]