问图算法
EN

Stack Overflow用户

提问于 2012-05-22 17:19:27

回答 1查看 117关注 0票数 1

设G是一个有n个顶点且都是孤立的图，n−1边，其中n≥2。证明了G至少包含两个1次顶点。

我通过使用属性求和度=2\E=来尝试这个问题。这个问题能用鸽子洞原理来解决吗？

发布于 2012-05-29 07:43:45

我想不出用鸽子洞原理来解决这个问题的合理方法，我会这样做：

度之和= 2n -2=2

由于没有顶点可以被隔离，所有的顶点都必须有至少1的度，所以有n-2‘备用’边缘端来连接。n-2东西要放进n个地方意味着至少有2个必须是空的(这类似于鸽子洞原理，但有点相反)，所以至少有2个顶点必须有1级。

我想你最好在这里问这样的问题：https://math.stackexchange.com/

票数 1

页面原文内容由Stack Overflow提供。腾讯云小微IT领域专用引擎提供翻译支持

原文链接：

https://stackoverflow.com/questions/10706904

复制

相似问题

问图算法EN