一个有至少2个顶点的简单图必定至少有2个度数相同的顶点
来源:百度知道 编辑:UC知道 时间:2024/06/22 20:19:32
3Q 20分送上.
在线等
而所有点对数都至多为k,k+1个点,这是啥意思???
在线等
而所有点对数都至多为k,k+1个点,这是啥意思???
对点数n归纳
n=2成立
设n=k成立n=k+1时
1)若有一点度数为0,去掉这点,则剩下k个点必有2个度数相同的顶点
2)若每点度数至少为1,而所有点对数都至多为k,k+1个点,度数都是1~k的整数,由抽屉原理得必定至少有2个度数相同的顶点
有归纳法对n=k+1也成立