np-completitude na árvore de abrangência de graus delimitados
Eu entendo por que a Árvore de Abrangência de Graus Limitados é considerada NP Completa com um grau ou 2 (é uma instância do Problema do Caminho Hamiltoniano), mas não entendo por que isso se aplica a graus> 2. Se alguém puder explicar por que isso é um problema NP completo para o grau> 2, seria muito útil