我正在准备考试和我的算法课程，我们一直需要涵盖 NP 完整性，但我们从来没有任何真正的教程，只是为考试提供了一堆“练习题”。除了最后一个，我已经完成了所有工作，我真的不知道如何解决它（到目前为止，询问互联网已经返回了我不理解的已发表论文）。
前两个问题表明哈密顿路径问题属于 NP 类，然后通过显示哈密顿循环问题简化为它来证明它是 NP 完全的。
这就引出了我似乎无法取得进展的第三个问题：
图的度数约束生成树是某个固定 k 的最大度数 k 的生成树（树中的每个顶点最多与 k 个边相邻）。确定图 G 是否包含度数受 k = 2 约束的生成树是哈密顿路径问题，这是一个 NP 完全问题，如您刚刚所示。证明决定图 G 是否包含度受 k 约束的生成树，对于一般 k，也是一个 NP 完全问题。
我目前回答这个问题的尝试是这样的：
对于 k = 2，对于任何顶点 V，我们可以将图拆分为 2 个不同的子图，它们仅共享顶点 V，并且对于哈密顿路径返回 true。也就是说，对于 k=3，有一个顶点 V，我们可以将图分成 3 个不同的子图，这些子图都具有哈密顿路径。
我知道这不正确，但我觉得它走在正确的道路上，但根本不知道如何达到最终目标。任何帮助，将不胜感激。