设G是有n个结点n条边的简单连通图,且G中存在度数为3的结点,证明G中至 ...

发布网友发布时间：2024-10-02 01:15

共2个回答

热心网友时间：2024-10-19 15:21

设D为结点度数
因为简单连通图
所以Di>=1且sum(Di)=2*n，1,2,...,n
因为存在Dx=3
所以剩余n-1个结点度数和为sum(Di)-Dx=2*n-3
假设不存在度数为1的结点
那么Di>=2
那么n-1个结点度数和>=2*(n-1)=2*n-2
因为2*n-3>=2*n-2矛盾
所以假设不成立，至少存在一个度数为1的结点

热心网友时间：2024-10-19 15:28

声明：本网页内容为用户发布，旨在传播知识，不代表本网认同其观点，若有侵权等问题请及时与本网联系，我们将在第一时间删除处理。E-MAIL:11247931@qq.com