给出一个连通的无向图，找到了具有最小最大度的生成树的问题（M.F，F，urr，B. Raghvachari，“逼近最小度生成树到最佳度内的一个”，ACM SIAM离散算法（SOD）专题讨论会，1992）。问题是NP-难，并在参考文献中描述了一种近似算法。
我感兴趣的是下面的问题-给定一个连通的无向图g=（v1，v2，e），找到在所有内部节点（非叶节点）上具有最大最小度的生成树。有人能告诉我这个问题是否已经被研究过，它是NP-难的还是存在一个多项式时间算法来解决它？此外，为了方便起见，图可以被认为是二部的。
最佳答案
正如evgeny kluev的评论所指出的，一棵（有限）树的叶子有1度。（否则，周期将存在，结构不会是树。）
如果是在一个连通的无向图G上，从所有可能生成树中寻找一个具有最大度的节点的生成树，那么就形成一个生成树，它的根R是G的所有节点之间的最大G的节点m，而M的所有邻居都是R的子。
关于algorithm - 查找具有最大最小度的生成树，我们在Stack Overflow上找到一个类似的问题：https://stackoverflow.com/questions/15464592/