“在顶点个数不少于2的简单无向图中,必有度数相同的顶点”的证明过程?
答案:1 悬赏:70 手机版
解决时间 2021-08-23 08:57
- 提问者网友：像風在裏
- 2021-08-22 08:33
“在顶点个数不少于2的简单无向图中,必有度数相同的顶点”的证明过程?
最佳答案
- 五星知识达人网友：十年萤火照君眠
- 2021-08-22 10:07
对点数n归纳
n=2成立
设n=k成立n=k+1时
1）若有一点度数为0,去掉这点,则剩下k个点必有2个度数相同的顶点
2）若每点度数至少为1,而所有点对数都至多为k,k+1个点,度数都是1至k的整数,由抽屉原理得必定至少有2个度数相同的顶点
归纳法对n=k+1也成立
所以在顶点个数不少于2的简单无向图中,必有度数相同的顶点
我要举报
如以上回答内容为低俗、色情、不良、暴力、侵权、涉及违法等信息，可以点下面链接进行举报！
点此我要举报以上问答信息
大家都在看
推荐资讯