给定一个连通的无向图，找到具有最小最大度的生成树的问题已得到充分研究（M. Fürer，B. Raghvachari，“将最小度生成树逼近到最佳度的一个范围内”， ACM-SIAM 离散算法研讨会 (SODA)，1992 年）。该问题是 NP-hard 问题，参考文献中已经描述了一种近似算法。
我对以下问题感兴趣 - 给定一个连接的无向图 G = (V1,V2,E)，在所有内部节点（非叶节点）上找到具有最大最小度的生成树。有人可以告诉我这个问题是否已经研究过；它是 NP-hard 还是存在解决它的多项式时间算法？此外，为方便起见，该图可以被认为是二分图。
看起来 3 组的精确覆盖可以减少到这个问题。用 4 度的顶点表示 3 组，每组都有 3 条边将其连接到 3 个节点，这些节点表示其在原始问题实例中的元素。附加的第 4 条边将所有“3-set”节点连接到单个顶点 V。
这个图是二分的——每条边都在一个“3-set”节点和一个“element”节点（或 V）之间。现在，当且仅当原始问题有解决方案时，此图具有最大最小度 = 4 的生成树。
显然需要有足够的 3 组，以便节点 V 不会降低树的最大最小度数，但是这个限制不会改变问题的 NP 难度。
正如 Evgeny Kluev 的评论中所指出的，（有限）树的叶子的度数为 1。（否则，循环将存在并且结构不会是树。）
相反，如果您的意思是从连通无向图 G 上的所有可能生成树中找到具有最大度数的节点的生成树，则只需形成一棵生成树，其根 R 是 G 的所有节点中度数最大的节点 M G 的节点，M 的所有邻居都是 R 的子节点。