证明:N个顶点的简单图最少有2个顶点度数一样

wegtdfhdfjtr 1年前 已收到1个回答 举报

没收我的爱 花朵

共回答了19个问题采纳率:89.5% 举报

对点数n归纳
n=2成立
设n=k成立n=k+1时
1)若有一点度数为0,去掉这点,则剩下k个点必有2个度数相同的顶点
2)若每点度数至少为1,而所有点对数都至多为k,k+1个点,度数都是1至k的整数,由抽屉原理得必定至少有2个度数相同的顶点
归纳法对n=k+1也成立
所以在顶点个数不少于2的简单无向图中,必有度数相同的顶点

1年前

5
可能相似的问题
Copyright © 2024 YULUCN.COM - 雨露学习互助 - 17 q. 1.319 s. - webmaster@yulucn.com